JAVA O(MN^2 * logM) solution


  • 0
    D

    assuming that m>>n, same idea with the solution of "Max Sum of SubArray No Larger than K".

    public class Solution {
        public int maxSumSubmatrix(int[][] matrix, int k) {
            int m = matrix.length, n=matrix[0].length, global=Integer.MIN_VALUE;
            //generate sums for all rectangles starting from (0,0)
            int[][] sums = new int[m][n];
            sums[0][0] = matrix[0][0];
            for (int j=1; j<n; j++) sums[0][j] = sums[0][j-1]+matrix[0][j];
            for (int i=1; i<m; i++) {
                int running = 0;
                for (int j=0; j<n; j++) {
                    running += matrix[i][j];
                    sums[i][j] = sums[i-1][j] + running;
                }
            }
            //assuming m>>n
            for (int j1=0; j1<n; j1++) {
                for (int j2=j1; j2<n; j2++) {
                    TreeSet<Integer> helper= new TreeSet<Integer>();
                    helper.add(0);
                    for (int i=0; i<m; i++) {
                        int cur = sums[i][j2] - (j1>0 ? sums[i][j1-1] : 0);
                        Integer ceil = helper.ceiling(cur - k);
                        if (ceil!=null) {
                            int local = cur - ceil;
                            global = Math.max(global, local);
                        }
                        helper.add(cur);
                    }
                }
            }
            return global;
        }
    }
    

Log in to reply
 

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