难度: Medium
给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。
返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。
示例 1：
输入：arr = [1,15,7,9,2,5,10], k = 3 输出：84 解释：数组变为 [15,15,15,9,10,10,10]
示例 2：
输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4 输出：83
示例 3：
输入：arr = [1], k = 1 输出：1
提示：
1 <= arr.length <= 5000 <= arr[i] <= 1091 <= k <= arr.length运行时间: 80 ms
内存: 16.1 MB
class Solution:
def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
n = len(arr)
dp = [0] * n
max_val = dp[0] = arr[0]
for i in range(1, k):
if arr[i] > max_val:
max_val = arr[i]
dp[i] = max_val * (i + 1)
for i in range(k, n):
max_val = arr[i]
res = dp[i - 1] + max_val
for j in range(2, k + 1):
if arr[i - j + 1] > max_val:
max_val = arr[i - j + 1]
temp = dp[i - j] + max_val * j
if temp > res:
res = temp
dp[i] = res
return dp[-1]
该题解采用了动态规划的策略来解决问题。定义一个dp数组，其中dp[i]表示到数组arr中第i个元素为止的最大和。初始化dp[0]为arr[0]。对于前k个元素，更新dp[i]为前i+1个元素中的最大值乘以i+1。对于第k个元素之后的每个元素，考虑所有可能的分割方式（最多k个元素为一组），计算每种方式下的最大和，更新dp[i]为所有这些可能中的最大值。
时间复杂度: O(n*k)
空间复杂度: O(n)
class Solution:
def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
n = len(arr)
dp = [0] * n # dp数组初始化
max_val = dp[0] = arr[0] # 初始化第一个元素
for i in range(1, k):
if arr[i] > max_val:
max_val = arr[i] # 更新当前最大值
dp[i] = max_val * (i + 1) # 更新dp数组
for i in range(k, n):
max_val = arr[i]
res = dp[i - 1] + max_val # 计算以当前元素单独分割的情况
for j in range(2, k + 1):
if arr[i - j + 1] > max_val:
max_val = arr[i - j + 1] # 更新区间最大值
temp = dp[i - j] + max_val * j # 计算当前分割的总和
if temp > res:
res = temp # 寻找最大的分割方案
dp[i] = res # 更新dp数组
return dp[-1] # 返回最终的最大和
在处理前k个元素时，由于分割的最大长度是k，因此可以将前i+1个元素视为一个整体进行考虑，其最大和可以通过取这个区间内的最大值乘以区域长度（即i+1）来实现。这种方法并没有忽略分割方式，因为在这个阶段内，任何分割都不会超过k个元素，而最优的分割方式就是取最大值乘以整个区域的长度，这样可以保证这部分的和是最大的。
在更新dp[i]时需要考虑以当前元素结尾的最长为k的所有子数组，并计算它们的最大可能和，这就需要遍历这些子数组来找到最大值。这个过程确实涉及到重复的最大值计算，可以通过使用滑动窗口的技术或者维护一个递减的双端队列来优化这个过程，这样可以在常数时间内获取到最大值，从而减少重复计算。
选择最大值乘以子数组的长度作为分割总和是基于这样一个观察：在限定子数组长度的情况下，最大化子数组的和可以通过选择最大的元素并使其影响尽可能大的范围来实现。这种方法在大部分情况下可以得到最优解，尤其是在题目约束中，分割后的每个子数组长度不超过k，且求最大和的情况下。然而，这种方法基于贪心算法的思想，在一些特殊配置的输入下可能不会得到全局最优解，但在大多数实际应用场景中是有效的。
dp数组中的每个值dp[i]代表考虑到数组arr的第i个元素为止，可以获得的最大和。具体计算过程如下：对于数组的每个元素i，如果i小于k，则dp[i]更新为从开始到当前元素的最大值乘以当前元素的索引加一。如果i大于等于k，则需要考虑所有可能的分割方式，即遍历之前的最多k个元素，计算每种情况下的可能最大和，并更新dp[i]为这些值中的最大值。这种方式确保了在每个阶段，dp[i]都存储了到当前元素为止可能达到的最大和。