Python程式：求解最大K個子列表之和

假設我們有一個名為nums的數字列表，還有一個值k，它表示nums列表連線k次的較長列表。我們需要找到具有最大和的連續子列表的和。

因此，如果輸入類似於nums = [1, 3, 4, -5]，k = 1，則輸出將為11，因為我們可以取[2, 4, 5]這樣的子列表。(原文例子有誤，此處修正為更合理的解釋)

為了解決這個問題，我們將遵循以下步驟：

  • s := ans := lo := 0
  • 對於範圍0到min(k, 2)中的所有值，執行：
    • 對於nums中的每個x，執行：
      • s := s + x
      • lo := min(lo, s)
      • ans := max(ans, s - lo)
  • 返回 ans + max(0, nums所有元素之和 * max(0, k - 2))

讓我們看看下面的實現，以便更好地理解：

示例

線上演示

class Solution:
   def solve(self, nums, k):
      s = ans = lo = 0
      for _ in range(min(k, 2)):
         for x in nums:
            s += x
            lo = min(lo, s)
         ans = max(ans, s - lo)
      return ans + max(0, sum(nums)) * max(0, (k - 2))
ob = Solution()
nums = [2, 4, 5, -4]
k = 1
print(ob.solve(nums, k))

輸入

[2, 4, 5, -4], 1

輸出

11

更新於：2020年11月19日

215 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告