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+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告