本文主要是介绍LeetCode面试题 17.24. Max Submatrix LCCI——压缩数组+动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 一、题目
- 二、题解
一、题目
Given an NxM matrix of positive and negative integers, write code to find the submatrix with the largest possible sum.
Return an array [r1, c1, r2, c2], where r1, c1 are the row number and the column number of the submatrix’s upper left corner respectively, and r2, c2 are the row number of and the column number of lower right corner. If there are more than one answers, return any one of them.
Note: This problem is slightly different from the original one in the book.
Example:
Input:
[
[-1,0],
[0,-1]
]
Output: [0,1,0,1]
Note:
1 <= matrix.length, matrix[0].length <= 200
二、题解
class Solution {
public:vector<int> getMaxMatrix(vector<vector<int>>& matrix) {int n = matrix.size(),m = matrix[0].size();int maxVal = INT_MIN;int a = 0,b = 0,c = 0,d = 0;for(int up = 0;up < n;up++){vector<int> nums(m,0);for(int down = up;down < n;down++){for(int l = 0,r = 0,pre = INT_MIN;r < m;r++){nums[r] += matrix[down][r];if(pre > 0) pre += nums[r];else {pre = nums[r];l = r;}if(pre > maxVal){maxVal = pre;a = up;b = l;c = down;d = r;}}}}return {a,b,c,d};}
};
这篇关于LeetCode面试题 17.24. Max Submatrix LCCI——压缩数组+动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
