动态规划
枚举所有子矩阵并压缩矩阵,将二维边一维,以下面矩阵为例
2 -6 2
1 -4 1
8 0 -2
子矩阵为{1}. {1. 2}, {1, 2, 3}, {2}, {2, 3}, {3}
拿{1, 2, 3}为例,该状态表示的是答案具有三行x列的情况。将每一列各行元素相加得到
第一列:2 + 1 + 8 = 11
第二列:-6 - 4 + 0 = -10
第三列:2 + 1 - 2 = 1
问题就转化为最大子段和,即第一列(三行一列)
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110;
int d[N][N], dp[N], res = -128, n;
int main() {
cin >> n;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) cin >> d[i][j];
}
for(int l = 1; l <= n; ++l) {
for(int r = l; r <= n; ++r) {
memset(dp, 0, sizeof dp);
for(int i = l; i <= r; ++i) {
for(int j = 1; j <= n; ++j) {
dp[j] += d[i][j];
}
}
for(int i = 1; i <= n; ++i) {
dp[i] = max(dp[i], dp[i - 1] + dp[i]);
res = max(res, dp[i]);
}
}
}
cout << res;
return 0;
}