给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。
用滚动数组优化，问题转化为求若干次最大子数组。
class Solution {
public:
vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
vector<vector<int>> M(n+1, vector<int>(m+1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
M[i][j] = matrix[i-1][j-1];
}
}
vector<int> ans(4);
vector<int> a(m+1);
int L, R, sum = -1e9;
int mx = -1e9;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[j] = 0;
}
for (int j = i; j <= n; j++) {
sum = -1e9;
for (int l = 1, r = 1; r <= m; r++) {
a[r] += M[j][r];
if (sum >= 0) {
sum += a[r];
} else {
sum = a[r];
l = r;
}
if (sum > mx) {
mx = sum;
ans[0] = i-1, ans[1] = l-1;
ans[2] = j-1, ans[3] = r-1;
}
}
}
}
return ans;
}
};