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: 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; }