Java DP O(m*m*n*n) solution, 262 ms


  • 0

    Use a sum array to store the accumulated sum value of each row. And then calculate all the possible values ( check each sum[i1...i2][j1....j2])

    public class Solution {
        public int maxSumSubmatrix(int[][] matrix, int k) {
            int m = matrix.length;
            if(m < 1)return 0;
            int n = matrix[0].length;
            int[][] sum = new int[m+1][n+1];
            for(int j = 1; j <= n; j++){
                for(int i = 1; i <= m; i++){
                    sum[i][j] = sum[i][j-1] + matrix[i-1][j-1];
                }
            }
            int res = Integer.MIN_VALUE;
            for(int j = 0; j < n; j++){
                for(int j2 = j+1; j2 <= n; j2++){
                    int[] row = new int[m+1];
                    int[] sumRow = new int[m+1];
                    for(int i = 1; i <= m; i++){
                        row[i] = sum[i][j2] - sum[i][j];
                        sumRow[i] = sumRow[i-1]+row[i];
                    }
                    for(int i = 0; i < m; i++){
                        for(int i2 = i+1; i2 <= m; i2++){
                            int tmp = (sumRow[i2] - sumRow[i]);
                            if(tmp <= k && tmp > res){
                                res = tmp;
                                if(tmp == k)return k;
                            }
                        }
                    }
                }
            }
            return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.