[Java] 244ms Applying


  • 1

    Refer to This solution

    public class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        //Assuming that rows is larger than the number of cols
    
        int row=matrix.length, col=matrix[0].length;
        int minDf=Integer.MAX_VALUE;
        for(int left=0;left<col;left++){
            int[] tmp=new int[row];
            for(int right=left;right<col;right++){
                TreeSet<Integer> set=new TreeSet<>();
                int cursum=0;
                for(int i=0;i<row;i++){
                    tmp[i]+=matrix[i][right];
                    cursum+=tmp[i];
                    if(cursum==k) return k;
                    if(cursum<k) minDf=Math.min(minDf,k-cursum);
                    Integer x=set.ceiling(cursum-k);
                    if(x!=null && cursum-x<=k) minDf=Math.min(minDf,k-cursum+x);
                    if(minDf==0) return k;
                    set.add(cursum);
                }
            }
        }
        return k-minDf;
    }
    

    }


Log in to reply
 

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