poj1050:http://poj.org/problem?id=1050
题意：给你一个n*n的矩阵，求一个和最大的一个子矩阵。
题解： 从第i行开始，对把i行以后的每一行一次加到第i行上，每加一次，求一遍最大子序列的和。然后枚举每一行，更新ans值。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 int a[102][102]; 7 int temp[102]; 8 int n,ans; 9 void in(){ 10 memset(a,0,sizeof(a)); 11 for(int i=1;i<=n;i++) 12 for(int j=1;j<=n;j++) 13 scanf("%d",&a[i][j]); 14 } 15 void solve(){ 16 ans=-100000000; 17 for(int i=1;i<=n;i++){ 18 int maxn=0; 19 for(int k=1;k<=n;k++)//取出每一行 20 temp[k]=a[i][k]; 21 for(int s=1;s<=n;s++){//对该行求一遍最大连续子序列的和 22 maxn+=temp[s]; 23 if(maxn>ans)ans=maxn;//更新ans值 24 if(maxn<0)maxn=0; 25 } 26 for(int j=i+1;j<=n;j++){//对把i行以后的每一行一次加到第i行上 27 maxn=0; 28 for(int h=1;h<=n;h++) 29 temp[h]+=a[j][h]; 30 for(int t=1;t<=n;t++){//对新的temp数组进行求值 31 maxn+=temp[t]; 32 if(maxn>ans)ans=maxn;//更新ans值 33 if(maxn<0)maxn=0; 34 } 35 } 36 } 37 } 38 int main(){ 39 while(~scanf("%d",&n)){ 40 in(); 41 ans=0;//初始化ans值 42 solve(); 43 printf("%d ",ans); 44 } 45 }