Minimum Total Space Wasted With K Resizing Operations LeetCode solution in JavaScript

1
var minSpaceWastedKResizing = function (nums, k) {
2
  var prefixSum = []; // prefix is index 1 based
3
  var rangeMax = []; // index 0 based
4
  var sum = 0;
5
  prefixSum[0] = 0;
6
  for (var i = 0; i < nums.length; i++) {
7
    sum += nums[i];
8
    prefixSum[i + 1] = sum;
9
  }
10
  for (var i = 0; i < nums.length; i++) {
11
    var max = -Infinity;
12
    rangeMax[i] = [];
13
    for (var j = i; j < nums.length; j++) {
14
      max = Math.max(nums[j], max);
15
      rangeMax[i][j] = max;
16
    }
17
  }
18
  var f = []; // f[i][j] is resize i times to get minimun with index j - 1 to get minimum space.
19
  f[0] = [];
20
  for (var i = 0; i <= k; i++) {
21
    f[i] = [];
22
    f[i][0] = 0;
23
  }
24
  for (var j = 1; j <= nums.length; j++) {
25
    f[0][j] = rangeMax[0][j - 1] * j - prefixSum[j];
26
  }
27

28
  for (var i = 1; i <= k; i++) {
29
    for (var j = 1; j <= nums.length; j++) {
30
      f[i][j] = Infinity;
31
      for (var m = 1; m <= j; m++) {
32
        f[i][j] = Math.min(
33
          f[i][j],
34
          f[i - 1][m - 1] +
35
            rangeMax[m - 1][j - 1] * (j - m + 1) -
36
            (prefixSum[j] - prefixSum[m - 1])
37
        );
38
      }
39
    }
40
  }
41
  return f[k][nums.length];
42
};