题目名称

给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。

返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。

示例

输入：arr = [1,15,7,9,2,5,10], k = 3
输出：84
解释：数组变为 [15,15,15,9,10,10,10]

输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
输出：83

题解

这个题讲道理，没有想到可以用动态规划的形式来做，本来一开始打算的是求出最大值，然后根据最大值周围的情况来进行数据的替换，但是总有一部分用例不满足。

啥也不说了，先看一下使用动态规划的一个逻辑是啥。

首先创建一个长度为n + 1 的一个数组，初始值都为0，目的是为了存储当前位置的计算之后的最大值。

然后通过遍历循环，针对每个位置 i 进行计算当前位置的最大值，计算逻辑如下

  1. 首先，将分离后的子数组的最大值置为i所在位置。
  2. 通过遍历 i 的前 k 位的子数组和的最大值 + 当前子数组最大值 * 子数组长度，然后通过比较最大值，设置为 i 当前的子数组和的最大值
  3. 把当前子数组最大值与当前位置 j 的值进行比较，取最大值
  4. 这样遍历完成后就得到一个每个位置最大值的数组，取最后一个元素即可

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
 var maxSumAfterPartitioning = function(arr, k) {
  const n = arr.length;
  const d = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
      let maxValue = arr[i - 1];
      // 根据第i位，向前推k位，然后分别将对应元素与推的个数的乘积的最大值
      for (let j = i - 1; j >= Math.max(0, i - k); j--) {
          d[i] = Math.max(d[i], d[j] + maxValue * (i - j));
          if (j > 0) {
              maxValue = Math.max(maxValue, arr[j - 1]);
          }
      }
  }
  return d[n];

};

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