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

1
/**
2
 * @param {number[][]} matrix
3
 * @param {number} k
4
 * @return {number}
5
 */
6
var maxSumSubmatrix = function (matrix, k) {
7
  if (!matrix.length) return 0;
8

9
  let n = matrix.length,
10
    m = matrix[0].length;
11
  let sum = new Array(n + 1).fill(0).map((a) => new Array(m + 1).fill(0));
12
  let ans = -Infinity;
13

14
  for (let i = 1; i <= n; i++) {
15
    for (let j = 1; j <= m; j++) {
16
      sum[i][j] =
17
        matrix[i - 1][j - 1] +
18
        sum[i - 1][j] +
19
        sum[i][j - 1] -
20
        sum[i - 1][j - 1];
21
      for (let x = 1; x <= i; ++x) {
22
        for (let y = 1; y <= j; ++y) {
23
          let s = rangeSum(sum, x, y, i, j);
24
          if (s <= k) {
25
            ans = Math.max(s, ans);
26
          }
27
        }
28
      }
29
    }
30
  }
31
  return ans;
32
};
33

34
const rangeSum = (sum, x1, y1, x2, y2) => {
35
  return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
36
};