POJ 2479/POJ 2593的拓展，從一維數(shù)組變成了二維矩陣，不過(guò)我們可以把情況模擬成一維的情況，在DP的基礎(chǔ)上需要加上枚舉。
題目要求求出給定的一個(gè)矩陣的和最大的子矩陣。
我們可以枚舉第a行到第c行的情況（假設(shè)已經(jīng)確定矩陣已經(jīng)確定為最上面為第a行，最下面為第c行），那么只需要確定列的范圍即可。我們可以把每一列都求和，這樣會(huì)得到單獨(dú)的一行，就可以直接求這一行的最大子段和即可。
1 #include <stdio.h>
2 #include <string.h>
3
4 #define MAX_NUM (100 + 10)
5
6 int main(int argc, char **argv)
7 {
8 //freopen("in.txt", "r", stdin);
9 //freopen("out.txt", "w", stdout);
10
11 short dic[MAX_NUM][MAX_NUM];
12 short tmp[MAX_NUM];
13 int n, i, j, top, bottom, res, tsum;
14
15 while (EOF != scanf ("%d", &n))
16 {
17 for (i = 0; i < n; ++i)
18 {
19 for (j = 0; j < n; ++j)
20 {
21 scanf ("%d", &dic[i][j]);
22 }
23 }
24 res = -99999;
25 for (top = 0; top < n; ++top)
26 {
27 for (bottom = top; bottom < n; ++bottom)
28 {
29 tsum = 0;
30 for (i = 0; i < n; ++i)
31 {
32 tmp[i] = 0;
33 for (j = top; j <= bottom; ++j)
34 {
35 tmp[i] += dic[j][i];
36 }
37 tsum += tmp[i];
38 if (tsum > res)
39 res = tsum;
40 if (tsum < 0)
41 tsum = 0;
42 }
43 }
44 }
45 printf ("%d\n", res);
46 }
47
48 return 0;
49 }