NYOJ 104 最大和

http://acm.nyist.net/JudgeOnline/problem.php?pid=104

看了下别人的解题报告, 才知道原来还是相当于一维的数组的最大子序列的问题....

只是将二维的数组转换为一维的数组继续求最大子序列

View Code

 1 #include <stdio.h>
 2 #define maxn 101
 3 int ans[maxn], temp[maxn][maxn];
 4 int row(int n, int ans[])
 5 {
 6     int i, b=0, sum=-1000000;
 7     for(i=0; i<n; i++)
 8     {
 9         if(b > 0) b += ans[i];
10         else b = ans[i];
11         if(sum < b) sum = b;
12     }
13     return sum;
14 }
15 int Maxmatrix(int n, int m)
16 {
17     int i, j, l, sum=-100000, max;
18     for(i = 0; i < n; i++)
19     {
20         for(j = 0; j < m; j++)
21         ans[j] = 0;
22         for(j = i; j < n; j++)
23         {
24             for(l = 0; l < m; l++)
25             ans[l] += temp[j][l];
26             max = row(l, ans);
27             if(max > sum ) sum = max;
28         }
29     }
30     return sum;
31 }
32 
33 int main()
34 {
35     int i, j, t, r, c;
36     scanf("%d",&t);
37     while(t--)
38     {
39         scanf("%d%d",&r,&c);
40         for(i = 0; i < r; i++)
41          for(j = 0; j < c; j++)
42          scanf("%d",&temp[i][j]);
43         printf("%d\n",Maxmatrix(r,c)); 
44     }
45 
46 }