Python程式：查詢環形子列表的最大和

假設我們有一個數字列表nums，現在考慮一個nums的環形列表，其中nums的開頭和結尾是相鄰的。我們必須找到環形列表中非空子列表的最大和。

因此，如果輸入類似於nums = [2, 3, -7, 4, 5]，則輸出將為14，因為我們可以取子列表[4, 5, 2, 3]，其和為14。

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

  • max_sum := 負無窮大，cur_max := 0

  • min_sum := 正無窮大，cur_min := 0

  • 對於nums中的每個num，執行：

    • cur_max := num和cur_max + num中的最大值

    • max_sum := max_sum和cur_max中的最大值

    • cur_min := num和cur_min + num中的最小值

    • min_sum := min_sum和cur_min中的最小值

  • 如果max_sum <= 0，則

    • 返回max_sum

  • 返回max_sum和(nums中所有元素的和 - min_sum)中的最大值

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

示例

import math
class Solution:
   def solve(self, nums):
      max_sum = -math.inf
      cur_max = 0
      min_sum = math.inf
      cur_min = 0
      for num in nums:
         cur_max = max(num, cur_max + num)
         max_sum = max(max_sum, cur_max)
         cur_min = min(num, cur_min + num)
         min_sum = min(min_sum, cur_min)
      if max_sum <= 0:
         return max_sum
      return max(max_sum, sum(nums) - min_sum)
ob = Solution()
nums = [2, 3, -7, 4, 5]
print(ob.solve(nums))

輸入

[2, 3, -7, 4, 5]

輸出

14

更新於：2020年10月9日

瀏覽量：195

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告