Daily Archives: June 29, 2016

This is a variation of this post. Besides finding the max continuous subarray, it requires that the max value should be less or equal to K.

The solution is to store all the sum[right] for arr[0, …, right]. Then try to find the sum[left] for arr[0, …, left], which we can get max(sum[right] – sum[left]) and sum[right] – sum[left] <= k. See below description:

So, when we have sumRight and k, we try to find the sumLeft, which is equal to or greater than sumRight – k. In order to achieve this, we can use TreeSet.

Below is the code for this problem. A important part of this code is that we should add 0 into TreeSet, or it won’t pass case like ({1, 0}, 2) or ({2}, 2)

public static int maxSubArrayLessThanK(int []arr, int k) {
    int ans = Integer.MIN_VALUE, sumRight = 0;
    TreeSet<Integer> ts = new TreeSet<>();
    ts.add(0);  // this is important. without this, won't pass {1, 0}
    for (int i : arr) {
        sumRight += i;
        Integer sumLeft = ts.ceiling(sumRight - k);
        if (sumLeft != null) {
           ans = Math.max(ans, sumRight - sumLeft);
        }
        ts.add(sumRight);
    }
    return ans;
}

Finally, let’s jump to the leetcode problem: Max Sum of Rectangle No Larger Than K. Since we went through this problem and previous max subarray problem, this rectangle no larger than K problem can be solved naturally:

public static int maxSubArrayRectangleLessThanK(int [][]matrix, int k) {
    int ans = Integer.MIN_VALUE, row = matrix.length, col = matrix[0].length;
    for (int left = 0; left < col; left++) {
        int[] helper = new int[row];
        for (int right = left; right < col; right++) {
            for (int i = 0; i < helper.length; i++) {
                helper[i] += matrix[i][right];
            }
            int sumRight = 0;
            TreeSet<Integer> ts = new TreeSet<>();
            ts.add(0);  // this is important. without this, won't pass {1, 0}
            for (int i : helper) {
                sumRight += i;
                Integer sumLeft = ts.ceiling(sumRight - k);
                if (sumLeft != null) {
                    ans = Math.max(ans, sumRight - sumLeft);
                }
                ts.add(sumRight);
            }   // for
        }   // for
    }
    return ans;
}

Check my code on github: MaxSubarrayLessThanK, MaxSubarrayRectangleLessThanK