面試題 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};}
}