URAL 1146 Maximum Sum（DP）

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int MAXN = 110;
 8 
 9 int mat[MAXN][MAXN], n;
10 int sum[MAXN][MAXN];
11 
12 void calsum() {
13     for(int i = 1; i <= n; ++i)
14         for(int j = 1; j <= n; ++j) sum[i][j] = sum[i - 1][j] + mat[i][j];
15 }
16 
17 int solve() {
18     int ans = -999;
19     for(int r1 = 1; r1 <= n; ++r1) {
20         for(int r2 = r1; r2 <= n; ++r2) {
21             int t = 0;
22             for(int j = 1; j <= n; ++j) {
23                 t += sum[r2][j] - sum[r1 - 1][j];
24                 ans = max(t, ans);
25                 if(t < 0) t = 0;
26             }
27         }
28     }
29     return ans;
30 }
31 
32 int main() {
33     scanf("%d", &n);
34     for(int i = 1; i <= n; ++i)
35         for(int j = 1; j <= n; ++j) scanf("%d", &mat[i][j]);
36     calsum();
37     printf("%d\n", solve());
38 }