1
/** https://leetcode.com/problems/partition-array-for-maximum-sum/
2
 * @param {number[]} arr
3
 * @param {number} k
4
 * @return {number}
5
 */
6
var maxSumAfterPartitioning = function (arr, k) {
7
  // Array to hold max value for each integer in `arr`
8
  let dp = Array(arr.length).fill(0);
9
  dp[0] = arr[0];
10

11
  // Calculate max value for each integer
12
  for (let i = 1; i < arr.length; i++) {
13
    // The `maxK` is largest number from `i` to `i - k - 1`
14
    let maxK = 0;
15

16
    // The `maxVal` is for holding max value to be added to `dp[i]`
17
    let maxVal = 0;
18

19
    // Loop through `i` to `i - k - 1`
20
    for (let j = 1; j <= k; j++) {
21
      // Get max number
22
      maxK = Math.max(maxK, arr[i - (j - 1)]);
23

24
      // Calculate `maxVal`, if current `i` is smaller than `k`, we don't need to continue
25
      if (i < j) {
26
        maxVal = Math.max(maxVal, maxK * j);
27
        break;
28
      }
29

30
      maxVal = Math.max(maxVal, dp[i - j] + maxK * j);
31
    }
32

33
    // Store `maxVal`
34
    dp[i] = maxVal;
35
  }
36

37
  return dp[dp.length - 1];
38
};