| 0 | ?2 | ?7 | 0 |
| 9 | 2 | ?6 | 2 |
| ?4 | 1 | ?4 | 1 |
| ?1 | 8 | 0 | ?2 |
| input | output |
|---|---|
4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 |
15 |
输入矩阵mat[i][j]：
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
sum[i][j]表示从mat[1][j]到mat[i][j]的总和：
0 2 -7 0
9 4 -13 2
5 5 -17 3
4 13 -17 1
这样可以枚举出从下到上的每一列的和。
for(int r1=1; r1<=n; r1++){
for(int r2=r1; r2<=n; r2++){
//循环每一列这样就可以遍历每一个子阵了。
//求的方法跟求子段的和一样
}
}
1 #include <stdio.h> 2 #include <iostream> 3 #define MAXN 110 4 using namespace std; 5 6 int n; 7 int mat[MAXN][MAXN]; 8 int sum[MAXN][MAXN]; 9 10 int main() 11 { 12 while( scanf("%d",&n)!=EOF ){ 13 for(int i=1; i<=n; i++){ 14 for(int j=1; j<=n; j++){ 15 scanf("%d",&mat[i][j]); 16 } 17 } 18 for(int i=1; i<=n; i++){ 19 for(int j=1; j<=n; j++){ 20 if(i==1){ 21 sum[i][j]=mat[i][j]; 22 }else{ 23 sum[i][j]=sum[i-1][j]+mat[i][j]; 24 } 25 } 26 } 27 int ans=-999; 28 for(int r1=1; r1<=n; r1++){ 29 for(int r2=r1; r2<=n; r2++){ 30 int temp=0; 31 for(int j=1; j<=n; j++){ 32 temp+=sum[r2][j]-sum[r1-1][j]; 33 ans=max( temp ,ans ); 34 if(temp<0)temp=0; 35 } 36 } 37 } 38 printf("%d\n",ans); 39 } 40 return 0; 41 }
Ural 1146 Maximum Sum,布布扣,bubuko.com
原文：http://www.cnblogs.com/chenjianxiang/p/3636726.html