Python 中的最大和数组分区

假设我们有一个整数数组 A，我们需要将其划分为长度最多为 K 的（连续的）子数组。分区后，每个子数组的值都会更改为该子数组的最大值。我们需要找到分区后给定数组的最大和。因此，如果输入类似于 [1, 15, 7, 9, 2, 5, 10] 且 k = 3，则输出将为 84。这是因为数组变为 [15, 15, 15, 9, 10, 10, 10]

为了解决这个问题，我们将遵循以下步骤：

  • 创建一个与 A 长度相同的数组 dp，并将其全部填充为 0
  • 对于 i 从 0 到 A 的长度 - 1
    • 如果 i – 1 >= 0，则 dp[i] = A[i] + dp[i - 1]，否则为 0
    • temp := A[i]
    • 对于 j 从 1 到 k – 1
      • 如果 i – j >= 0
        • index := i – j
        • temp := temp 和 A[i - j] 的最大值
        • 如果 index – 1 >= 0，则
          • dp[i] := dp[i] 和 (temp*(i – index + 1) + dp[index - 1]) 的最大值
        • 否则 dp[i] := dp[i] 和 0 的最大值
  • 返回 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

更新于：2020年4月30日

1K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告