//將第i行到第j行的每列求和，保存于csum，然后求最大字串和
1
#include<iostream>
2using namespace std;
3#define MAXN 100
4#define _INF -10000000
5
6int a[MAXN+1][MAXN+1];
7int csum[MAXN+1];
8
9int maxSubArray(int csum[],int n)
10
{
11
int b=0,max=_INF,j;
12 for(j=1;j<=n;j++)
13
{
14 if(b>0) b+=csum[j];
15 else b=csum[j];
16 if(b>max) max=b;
17
}
18 return max;
19
}
20
21int main()
22{
23 int n,i,j,k,t,res=_INF;
24 scanf("%d",&n);
25 for(i=1;i<=n;i++)
26 for(j=1;j<=n;j++)
27 scanf("%d",&a[i][j]);
28
29 for(i=1;i<=n;i++)
30 {
31 memset(csum,0,sizeof(csum));
32 for(j=i;j<=n;j++)
33 {
34 for(k=1;k<=n;k++)
35 csum[k]+=a[j][k];
36 t=maxSubArray(csum,n);
37 if(t>res) res=t;
38 }
39 }
40 printf("%d\n",res);
41 return 0;
42}
43
posted on 2009-05-02 13:58
wyiu 閱讀(108)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
POJ