Python中最大和的分区数组
假设我们有一个整数数组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