1: 8  (0 1 1 1 1)
2: 7   (1 1 1 2 2)
3: 7  (1 1 1 2 2)
4: 9  (1 2 2 2 2)
5: 8  (1 1 2 2 2)

9: 11 (2 3 2 2 2)
10: 7 (1 1 1 2 2)
11: 8 (1 1 2 2 2)

17: 14 (2 3 3 3 3)
18: 13 (2 2 3 3 3)

total: 92

do 4 each day

求一个矩阵中最大的二维矩阵(元素和最大).如:
1 20 3 4
2 34 5 1
1 15 3 0
中最大的是:
45
53
要求:(1)写出算法;(2)分析时间复杂度;(3)用 C 写出关键代码

http://en.wikipedia.org/wiki/Maximum_subarray_problem

/* Copyleft: Ming Lin <minggr@gmail.com> */
/* Reference: http://www.algorithmist.com/index.php/UVa_108 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DIMENSION 2

int **alloc_prefix_matrix(int row, int col)
{
	int **two_d_array;
	int *data;
	int len;
	int r;
	int i;

	r = row - DIMENSION + 1;
	two_d_array = malloc(sizeof(int*) * r);	
	len = sizeof(int) * r * col;
	data = malloc(len);
	memset(data, 0, len);

	for (i = 0; i < r; i++)
		two_d_array[i] = data + i * col;

	return two_d_array;
}

/*
 * prefix sum: http://en.wikipedia.org/wiki/Prefix_sum
 */
void calculate_prefix_matrix(int matrix[3][5], int row, int col, int **prefix_matrix)
{
	int r, c;
	int i;

	for (c = 0; c < col; c++) {
		for (r = 0; r < row - DIMENSION + 1; r++) {
			if (r == 0) {
				for (i = 0; i < DIMENSION; i++)
					prefix_matrix[0][c] += matrix[i][c];
			} else
				prefix_matrix[r][c] = prefix_matrix[r-1][c] - matrix[r-1][c] + matrix[r+DIMENSION-1][c];
		}
	}
}

int max_sub_1d_array(int **prefix_matrix, int cur_row, int total_col)
{
	int max;
	int cur;
	int c;

	max = 0;
	for (c = 0; c < DIMENSION; c++) {
		max += prefix_matrix[cur_row][c];
	}
	cur = max;

	for (c = 1; c < total_col - DIMENSION + 1; c++) {
		cur = cur - prefix_matrix[cur_row][c-1] + prefix_matrix[cur_row][c+DIMENSION-1];
		if (cur > max)
			max = cur;
	}

	return max;
}

int max_sub_2d_array(int **prefix_matrix, int row, int col)
{
	int max;
	int r;

	max = max_sub_1d_array(prefix_matrix, 0, col);
	for (r = 1; r < row; r++) {
		int tmp = max_sub_1d_array(prefix_matrix, r, col);
		if (tmp > max)
			max = tmp;
	}

	return max;
}

int main()
{
	int matrix[3][5] = {{1, 2, 0, 3, 4}, {2, 3, 4, 5, 1}, {1, 1, 5, 3, 0}};
	int row = 3;
	int col = 5;
	int **prefix_matrix;
	int max;

	prefix_matrix = alloc_prefix_matrix(row, col);
	calculate_prefix_matrix(matrix, row, col, prefix_matrix);
	max = max_sub_2d_array(prefix_matrix, row - DIMENSION + 1, col);
	printf("max=%d\n", max);
	
	return 0;
}