面试题 17.24. 最大子矩阵

面试题 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 n=matrix.length,m=matrix[0].length,max=Integer.MIN_VALUE;int lr=-1,lc=-1,rr=-1,rc=-1;for(int i=0;i<n;i++){int[] sum=new int[m];for(int j=i;j<n;j++){int pre=0,s=0;for(int k=0;k<m;k++){sum[k]+=matrix[j][k];pre+=sum[k];if(pre>max){max=pre;lr=i;lc=s;rr=j;rc=k;}if(pre<0){pre=0;s=k+1;}}}}return new int[]{lr,lc,rr,rc};} }

总结

以上是生活随笔为你收集整理的面试题 17.24. 最大子矩阵的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。