# 最大子矩阵

### 给定一个正整数和负整数组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。

[
[-1,0],
[0,-1]
]

1 <= matrix.length, matrix[0].length <= 200

#### 先看我写的（嘿嘿）

``````#include <iostream>
#include <vector>
using namespace std;

#define r 2
#define l 2
class Solution {
public:
int maxSubArray(vector<int>& nums, int& c1, int& c2) {
int b = 0, sum = INT_MIN,c1_temp;
for (int i = 0; i < nums.size(); i++) {
if (b > 0) {
b += nums[i];
} else {
b = nums[i];
c1_temp = i;
}
if (b > sum ) {
sum = b;
c2 = i;
c1=c1_temp;
}
}
return sum;
}
vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
int max, c1, c2, r1, r2, Max_final = INT_MIN, c1_final, c2_final;
r1 = r2 = c1_final = c2_final =c1=c2= 0;
vector<int> ans(4);
for (int i = 0; i < matrix.size(); i++) {
vector<int> li(matrix[0].size());  //默认值为0
for (int j = i; j < matrix.size(); j++) {
for (int k = 0; k < matrix[0].size(); k++) {
li[k] += matrix[j][k];
}
max = maxSubArray(li, c1, c2);
if (max > Max_final) {
Max_final = max;
r1 = i, r2 = j;
c1_final = c1, c2_final = c2;
}
}
}
ans[0] = r1;
ans[1] = c1_final;
ans[2] = r2;
ans[3] = c2_final;
return ans;
}
};

int main() {
int array[r][l] = {-1, 0,0,-1};
vector<vector<int>> matrix(r, vector<int>(l));
for (int i = 0; i < r; i++) {
for (int j = 0; j < l; j++) {
matrix[i][j] = array[i][j];
}
}
Solution s;
s.getMaxMatrix(matrix);
}``````

maxSubArray用来计算一行的字序列最大值，输出列的范围

getMaxMatrix通过调用maxSubArray，实现矩阵的计算。

#### 更新了算法的格式

``````
/*
1.动态规划，压缩成行矩阵
*/
#include <iostream>
#include <vector>
using namespace std;

int main() {
int m, n, MAX = 0, init_n, end_n;
cin >> m >> n;
vector<vector<int>> vec(m, vector<int>(n));
vector<int> ans(4);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> vec[i][j];
}
}
for (int i = 0; i < m; i++) {
vector<int> dp(n);
for (int j = i; j < m; j++) {
int sum = 0, b = 0;
for (int k = 0; k < n; k++) {
dp[k] += vec[j][k];
if (b > 0) {
b += dp[k];
} else {
b = dp[k];
init_n = k;
}
if (b > sum) {
sum = b;
end_n = k;
}
}
if (sum > MAX) {
MAX = sum;
ans[0] = i;
ans[1] = j;
ans[2] = init_n;
ans[3] = end_n;
}
}
}
cout << MAX<<endl;
cout<<ans[0]+1;
for(int i=1;i<4;i++){
cout<<' '<<ans[i]+1;
}
system("pause");
}``````