http://acm.hdu.edu.cn/showproblem.php?pid=1081
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 300 5 using namespace std; 6 const int inf=0x7fffffff; 7 8 int dp[maxn][maxn]; 9 int a[maxn][maxn]; 10 11 int main() 12 { 13 int n; 14 while(scanf("%d",&n)!=EOF) 15 { 16 for(int i=1; i<=n; i++) 17 { 18 dp[i][0]=0; 19 for(int j=1; j<=n; j++) 20 { 21 scanf("%d",&a[i][j]); 22 dp[i][j]=dp[i][j-1]+a[i][j]; 23 } 24 } 25 int max1=-inf; 26 for(int i=1; i<=n; i++) 27 { 28 for(int j=1; j<=i; j++) 29 { 30 int c=0; 31 for(int k=1; k<=n; k++) 32 { 33 c+=(dp[k][i]-dp[k][j-1]); 34 if(max1<c) 35 max1=c; 36 if(c<0) 37 c=0; 38 } 39 } 40 } 41 printf("%d ",max1); 42 } 43 return 0; 44 }