C++刷leetcode（面试题 17.24. 最大子矩阵）【动态规划转化成最大子序列和问题】
题目描述：给定一个正整数和负整数组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
返回一个数组 ，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。
注意：本题相对书上原题稍作改动
示例:
输入:
[
[-1,0],
]
输出:
解释: 输入中标粗的元素即为输出所表示的矩阵
说明：
1 <= matrix.length, matrix.length <= 200
vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
int pos1 = 0, pos2 = 0, pos3 = 0, pos4 = 0, globalmax = INT_MIN;
int row = matrix.size(), col = matrix.size();
int max_ = INT_MIN;
for(int i = 0; i < row; i++){
vector<int> temp(col, 0);
for(int j = i; j < row; j++){
int curmax = INT_MIN, temp1 = 0;
for(int k = 0; k < col; k++){
temp += matrix;
if(curmax <= 0){
temp1 = k;
curmax = temp;
}
else{
curmax += temp;
}
if(curmax > globalmax){
globalmax = curmax;
pos1 = i;
pos2 = temp1;
pos3 = j;
pos4 = k;
}
}
}
}
return {pos1, pos2, pos3, pos4};
}
参考链接：https://leetcode-cn.com/problems/max-submatrix-lcci/solution/zhe-yao-cong-zui-da-zi-xu-he-shuo-qi-you-jian-dao-/
页:
[1]