杭电1081（动态规划）

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define inf -0xfffffff
 4 //#include<stdlib.h>
 5 /*#include<iostream>
 6 #include<algorithm>
 7 using namespace std;*/
 8 
 9 
10 int main(){
11     int n, i, j, value[101][101], dp[101][101], max, zmax, k, sum;
12     while(scanf("%d", &n) != EOF){
13         memset(dp, 0, sizeof(dp));
14         for(i = 1; i <= n; i ++){
15             for(j = 1; j <= n; j ++){
16                 scanf("%d", &value[i][j]);
17                 dp[i][j] = dp[i - 1][j] + value[i][j];
18             }
19         }
20         zmax = inf;
21         for(i = 1; i <= n; i ++){
22             for(j = i; j <= n; j ++){
23                 max = inf;
24                 sum = 0;
25                 for(k = 1; k <= n; k ++){
26                     sum += dp[j][k] - dp[i - 1][k];
27                     if(sum > max){
28                         max = sum;
29                     }
30                     if(sum < 0){
31                         sum = 0;
32                     }
33                 }
34                 if(max > zmax){
35                     zmax = max;
36                 }
37             }
38         }
39         printf("%d\n", zmax);
40     }
41     return 0;
42 }