假设我们有一个整数数组A，我们必须将该数组划分为最大为K的（连续）个子数组。分区后，每个子数组的值都更改为该子数组的最大值。分区后，我们必须找到给定数组的最大和。因此，如果输入类似于[1、15、7、9、2、5、10]且k = 3，则输出为84。这是因为数组变为[15、15、15、9、10、10 ，10]
为了解决这个问题，我们将遵循以下步骤-
使一个数组dp的长度与A相同，并用0填充
对于范围从0到A-1的i
如果i – j> = 0
dp [i]：= dp [i]的最大值，并且（temp *（i – index + 1）+ dp [index-1]）
索引：= i – j
temp：= temp和A [i-j]的最大值
如果索引– 1> = 0，则
否则dp [i]：= dp [i]的最大值和0
如果i – 1> = 0，则dp [i] = A [i] + dp [i-1]否则为0
温度：= A [i]
对于1到k – 1的j
返回dp的最后一个元素
让我们看下面的实现以更好地理解-
class Solution(object): def maxSumAfterPartitioning(self, A, K): dp = [0 for i in range(len(A))] for i in range(len(A)): dp[i] = A[i] + (dp[i-1] if i-1>=0 else 0) temp = A[i] for j in range(1,K): if i-j>=0: index = i-j temp = max(temp,A[i-j]) dp[i] = max(dp[i],temp*(i-index+1) + (dp[index-1] if index-1 >=0 else 0)) return dp[-1] ob = Solution()print(ob.maxSumAfterPartitioning([1,15,7,9,2,5,10],3))
[1,15,7,9,2,5,10] 3
输出结果
84