1043.js

/** ------------------------------------------------------------------------------
 * 
 * 2024.02.03
 * 1043. Partition Array for Maximum Sum
 * https://leetcode.com/problems/partition-array-for-maximum-sum/description/?envType=daily-question&envId=2024-02-03
 * 
 ------------------------------------------------------------------------------ */
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var maxSumAfterPartitioning = function (arr, k) {
  const len = arr.length;
  let result = 0;

  if (arr && len >= 1 && len <= 500 && k >= 1 && k <= len) {
    let currMaxForPartition;
    let memo = [];
    memo[0] = arr[0];

    for (let i = 1; i < len; i++) {
      currMaxForPartition = 0;
      memo[i] = 0;

      for (let a = 1; a <= k && i - a + 1 >= 0; a++) {
        currMaxForPartition = Math.max(currMaxForPartition, arr[i - a + 1]);

        memo[i] = Math.max(memo[i], (i >= k ? memo[i - a] : 0) + a * currMaxForPartition);
      }
      result = memo[len - 1];
    }
    console.log(memo);
  }

  return result;
};

console.log(maxSumAfterPartitioning([1, 15, 7, 9, 2, 5, 10], 3));

/** ------------------------------------------------------------------------------
 * 
 * description
 * 
 ------------------------------------------------------------------------------ */
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
let maxSumAfterPartitioning = function (arr, k) {
  const dp = new Array(arr.length + 1).fill(0);

  for (let i = 1; i <= arr.length; ++i) {
    let maxNum = -Infinity;
    for (let j = 1; j <= k; ++j) {
      const start = i - j;
      if (start < 0) break;
      maxNum = Math.max(arr[start], maxNum);
      dp[i] = Math.max(maxNum * j + dp[start], dp[i]);
    }
  }

  return dp[arr.length];
};