1043. 分隔数组以得到最大和
给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。
返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。
示例 1：
输入：arr = [1,15,7,9,2,5,10], k = 3
输出：84
解释：数组变为 [15,15,15,9,10,10,10]
题解
先通过动态规划预处理出位置 i 前的一个子区间的最大值，即 max，再利用动态规划求出位置 i 的最优解，即将位置 i 之前分成一个长度为 j 的区间和一个长度为 i - j 的区间，前者的最大值即为 max。随着不断前进，将得到整个数组的解。注意在第二层循环中，我们需要设置 j 的起点，也就是确保至少一次划分，以方便初始化 dp[1~k]，也就是最开始为 arr[0], arr[0] * 2, arr[0] * 3, …。时间复杂度为 $O(n^2)$。
var maxSumAfterPartitioning = function(arr, k) {
const n = arr.length;
const dp = new Array(n + 1).fill(0); // dp[i] 表示将前 i 个元素分隔变换后能够得到的元素最大和
for (let i = 1; i <= n; i++) { // 遍历每个位置
let max = 0; // 初始化最大值
const deque = []; // 定义一个单调队列
// 从右到左遍历前 i 个元素，找出长度不超过 k 的子数组的最大值
for (let j = i - 1; j >= 0 && i - j <= k; j--) {
max = Math.max(max, arr[j]);
deque.unshift(max); // 将最大值加入队列头部
const length = i - j; // 子数组长度为 i-j
if (length === 1) { // 如果子数组长度为 1，直接使用该元素的值进行赋值
dp[i] = Math.max(dp[i], arr[j]);
} else { // 否则，使用最大值乘以当前长度与 dp[j] 中的较大值进行赋值
dp[i] = Math.max(dp[i], deque[0] * length + dp[j]);
}
}
}
return dp[n]; // 返回 dp[n] 即为答案
};