I am surprised it beats 100%


  • 0
    H

    Similar to iaming's solution which uses merge sort
    Calculate max rectangle sum before we merge

    public class Solution {
    private int res;

    public int maxSumSubmatrix(int[][] matrix, int k) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        res = Integer.MIN_VALUE;
        long[] sum = new long[m];
        long[] helper = new long[m];
        for (int j = 0; j < n; j++) {
            long[] sumRow = new long[m];
            for (int p = j; p < n; p++) {
                for (int i = 0; i < m; i++) {
                    sumRow[i] += matrix[i][p];
                    sum[i] = (i == 0 ? 0 : sum[i - 1]) + sumRow[i];
                }
                
                //for (long i : sum) System.out.print(i + " ");
                //System.out.println();
                sortAndRecord(sum, 0, m - 1, helper, k);
                if (res == k) return k;
            }
        }
        return res;
    }
    
    private void sortAndRecord(long[] sum, int left, int right, long[] helper, int k) {
        if (left == right) {
            if (sum[left] <= k) res = Math.max(res, (int)sum[left]);
            return;
        }
        
        int mid = left + (right - left) / 2;
        sortAndRecord(sum, left, mid, helper, k);
        sortAndRecord(sum, mid + 1, right, helper, k);
        
        merge(sum, helper, left, mid, right, k);
    }
    
    private void merge(long[] sum, long[] helper, int left, int mid, int right, int k) {
        for (int i = left; i <= right; i++) {
            helper[i] = sum[i];
        }
        
        int leftI = left, rightI = mid + 1;
        for (int i = rightI; leftI <= mid && i <= right; i++) {
            if (helper[i] - helper[leftI] <= k) {
                res = Math.max(res, (int)(helper[i] - helper[leftI]));
            }else {
                leftI++;
                i--;
            }
        }
        leftI = left;
        while (leftI <= mid && rightI <= right) {
            if (helper[leftI] < helper[rightI]) sum[left++] = helper[leftI++];
            else sum[left++] = helper[rightI++];
        }
        
        while (leftI <= mid) {
            sum[left++] = helper[leftI++];
        }
    }
    

    }


Log in to reply
 

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