网站制作哪家便宜,网站页面如何设计,国字类型网站有哪些内容,网站改版重新备案面试题 17.24. 最大子矩阵
给定一个正整数、负整数和 0 组成的 N M 矩阵#xff0c;编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2]#xff0c;其中 r1, c1 分别代表子矩阵左上角的行号和列号#xff0c;r2, c2 分别代表右下角的行号和列号。若有多个…面试题 17.24. 最大子矩阵
给定一个正整数、负整数和 0 组成的 N × M 矩阵编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2]其中 r1, c1 分别代表子矩阵左上角的行号和列号r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵返回任意一个均可。
注意本题相对书上原题稍作改动
示例
输入 [ [-1,0], [0,-1] ] 输出[0,1,0,1] 解释输入中标粗的元素即为输出所表示的矩阵
解题思路
二维转一维 遍历矩形的上下边界[i,j],维护sum[k]数组代表在上下边界固定的情况下第k列的总和。那么我们对sum数组求出的最大子序和就是当前下面边界的情况下最大的矩形总和
代码
class Solution {public int[] getMaxMatrix(int[][] matrix) {int nmatrix.length,mmatrix[0].length,maxInteger.MIN_VALUE;int lr-1,lc-1,rr-1,rc-1;for(int i0;in;i){int[] sumnew int[m];for(int ji;jn;j){int pre0,s0;for(int k0;km;k){sum[k]matrix[j][k];presum[k];if(premax){maxpre;lri;lcs;rrj;rck;}if(pre0){pre0;sk1;}}}}return new int[]{lr,lc,rr,rc};}
}
