难度：★★★☆☆
类型：数组
方法：动态规划

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

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

返回将数组分隔变换后能够得到的元素最大和。

注意，原数组和分隔后的数组对应顺序应当一致，也就是说，你只能选择分隔数组的位置而不能调整数组中的顺序。

示例 1：

输入：arr = [1,15,7,9,2,5,10], k = 3
输出：84
解释：
因为 k=3 可以分隔成 [1,15,7] [9] [2,5,10]，结果为 [15,15,15,9,10,10,10]，和为 84，是该数组所有分隔变换后元素总和最大的。
若是分隔成 [1] [15,7,9] [2,5,10]，结果就是 [1, 15, 15, 15, 10, 10, 10] 但这种分隔方式的元素总和（76）小于上一种。

示例 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 <= 500
0 <= arr[i] <= 109
1 <= k <= arr.length

解答

求解一维数组的划分方式，我们这里用动态规划解决。我们把题目所解决的问题称作求数组A的分隔最大和。

【数组定义】

定义一维数组dp，长度为len(A)+1，A是输入数组。dp[i]表示A[:i]（也就是下标i（不包括i）之前的所有元素组成的A的子数组）的分隔最大和。dp长度比A多1的原因是，我们需要考虑A[:0]这种空数组的情况。

【初始状态】

初始状态下，把dp所有位置处的值填充为0。

【递推公式】

为了求取某个位置处的结果dp[i]，我们需要从i位置往回看K个元素，也就是需要根据dp[i-k],dp[i-k+1]，一直到dp[i-1]，来求取dp[i]，这样做的目的是，题目要求我们，每一段子数组的长度最多是K，而且i位置往左的所有dp位置都已经算好了结果，是可以拿来用的，我们就要考虑以A[i]结尾的，长度从1开始一直到K的所有子数组划分方式，假设该子数组开始于j位置，j从i-K一直到i-1。

递推公式为：

dp[i] = max(dp[i], dp[j] + mx * (i - j))

其中mx为A[j:i]这A[:i]被划分的最后一段的最大值。

需要注意的是，i的遍历顺序需要从前往后，这一点毋庸置疑，但是j的遍历顺序需要从后往前，原因是我们的最后一段子数组A[j:i]的长度是从1开始一直增加到K的，mx作为临时最大值变量，也需要按照逆序的方式才能顺利更新为我们想要的结果。

from typing import List


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        n = len(A)
        dp = [0] * (n+1)
        for i in range(1, n+1):
            mx = -float('inf')
            for j in reversed(range(max(i - K, 0), i)):
                mx = max(mx, A[j])
                dp[i] = max(dp[i], dp[j] + mx * (i - j))
        return dp[n]

s = Solution()
print(s.maxSumAfterPartitioning([1,15,7,9,2,5,10], 3))

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析