Max Sum of Rectangle No Larger Than K LeetCode solution in Java

1
class Solution {
2

3
  public int maxSumSubmatrix(int[][] matrix, int k) {
4
    final int m = matrix.length;
5
    if (m < 1) {
6
      throw new IllegalArgumentException("empty matrix - no rows");
7
    }
8
    final int n = matrix[0].length;
9
    if (n < 1) {
10
      throw new IllegalArgumentException("empty matrix - no columns");
11
    }
12
    // Let's make our bottom-right sum matrix wider and higher by 1 each, so we don't go out of
13
    // range.
14
    // All of the values r >= m and c >= n should be 0 (and will default to 0 during array
15
    // construction).
16
    final int[][] brsum = new int[m + 1][n + 1];
17
    // Build up from bottom right, bottom to top and right to left.
18
    for (int r = (m - 1); r >= 0; --r) {
19
      for (int c = (n - 1); c >= 0; --c) {
20
        final int val = matrix[r][c];
21
        // did we happen to find a 1x1 rectangle at (r, c) which sums to k?
22
        if (val == k) {
23
          return val;
24
        }
25
        // Extend the sum: value + right + down - rightAndDown (because rightAndDown was added
26
        // twice)
27
        brsum[r][c] = matrix[r][c] + brsum[r][c + 1] + brsum[r + 1][c] - brsum[r + 1][c + 1];
28
      }
29
    }
30
    // Now, we search.
31
    int maxSum = Integer.MIN_VALUE;
32
    for (int r0 = 0; r0 < m; ++r0) {
33
      for (int rf = r0; rf < m; ++rf) {
34
        final int rfp1 = rf + 1; // Let's avoid computing rf + 1 many times.
35
        for (int c0 = 0; c0 < n; ++c0) {
36
          for (int cf = c0; cf < n; ++cf) {
37
            final int cfp1 = cf + 1; // Let's avoid computing cf + 1 multiple times.
38
            // Compute the sum for this rectangle: complete - right - lower + lower_right.
39
            final int sum = brsum[r0][c0] + brsum[rfp1][cfp1] - brsum[r0][cfp1] - brsum[rfp1][c0];
40
            // Did we happen to find a sum adding to k?  If not, did we find a larger sum less than
41
            // k?
42
            if (sum == k) {
43
              return sum;
44
            } else if (sum < k && sum > maxSum) {
45
              maxSum = sum;
46
            }
47
          }
48
        }
49
      }
50
    }
51
    return maxSum;
52
  }
53
}