0 | ?2 | ?7 | 0 |
9 | 2 | ?6 | 2 |
?4 | 1 | ?4 | 1 |
?1 | 8 | 0 | ?2 |
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 }
URAL 1146 Maximum Sum(DP),布布扣,bubuko.com
原文:http://www.cnblogs.com/oyking/p/3585576.html