LeetCode - 面试题17.24 最大子矩阵

动态规划

class Solution {
    
    public int[] getMaxMatrix(int[][] matrix) {
    
       int m = matrix.length;
       int n = matrix[0].length;
       int[] sum = new int[n];
       int[] ans = new int[4]; 
       int last = 0;
       int maxval = matrix[0][0];
       int begin = 0;
       for(int i = 0; i <m;i++){
    
           Arrays.fill(sum,0);
           for(int j = i; j < m;j++){
    
               sum[0] += matrix[j][0];
               last = sum[0];
               begin = 0;
               for(int k = 1; k < n;k++){
    
                   sum[k] += matrix[j][k];
                   if(last > 0){
    
                       last += sum[k];
                   }
                   else{
    
                       last = sum[k];
                       begin = k;
                   }
                   if(last > maxval){
    
                       maxval = last;
                       ans[0] = i;
                       ans[1] = begin;
                       ans[2] = j;
                       ans[3] = k;
                   }

               }
           }
       }
       return ans;
    }
}