> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/max-sum-of-rectangle-no-larger-than-k.md).

# Max Sum of Rectangle No Larger Than K

Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

**Example:**

```
Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2 
Explanation: Because the sum of rectangle [[0, 1], [-2, 3]] is 2,
             and 2 is the max number no larger than k (k = 2).
```

**Note:**

1. The rectangle inside the matrix must have an area > 0.
2. What if the number of rows is much larger than the number of columns?

```java
class Solution {
    private int maxSumSubArray(int[] arr, int k) {
        int max = Integer.MIN_VALUE;
        int currSum = 0;
        TreeSet<Integer> set = new TreeSet();
        set.add(0);
        for (int i = 0; i < arr.length; i++) {
            currSum += arr[i];
            Integer gap = set.ceiling(currSum - k);
            if (gap != null)
                max = Math.max(max, currSum - gap);
            set.add(currSum);
        }
        return max;
    }

    public int maxSumSubmatrix(int[][] matrix, int target) {
        if (matrix.length == 0)
            return 0;
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < matrix[0].length; i++) {
            int[] sum = new int[matrix.length];
            for (int j = i; j < matrix[0].length; j++) {
                for (int k = 0; k < matrix.length; k++)
                    sum[k] += matrix[k][j];
                int bestSum = maxSumSubArray(sum, target);
                ans = Math.max(ans, bestSum);
                if (ans == target)
                    return ans;
            }
        }
        return ans;
    }
}
```