解題思路:類似一維情況下的最大連續(xù)子串。
代碼:#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 110;
int n, a[maxn][maxn], r[maxn][maxn] , f[maxn];
int main() {
while(~scanf("%d", &n)) {
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d", &a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
r[i][j] = r[i-1][j] + a[i][j];
int ans = a[0][0];
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
for(int k=1;k<=n;k++) {
if(f[k-1] < 0) {
f[k] = r[j][k] - r[i-1][k];
} else {
f[k] = f[k-1] + r[j][k] - r[i-1][k];
}
if(f[k] > ans) ans = f[k];
}
printf("%d\n", ans);
}
return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 110;
int n, a[maxn][maxn], r[maxn][maxn] , f[maxn];
int main() {
while(~scanf("%d", &n)) {
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d", &a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
r[i][j] = r[i-1][j] + a[i][j];
int ans = a[0][0];
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
for(int k=1;k<=n;k++) {
if(f[k-1] < 0) {
f[k] = r[j][k] - r[i-1][k];
} else {
f[k] = f[k-1] + r[j][k] - r[i-1][k];
}
if(f[k] > ans) ans = f[k];
}
printf("%d\n", ans);
}
return 0;
}