Python 程式，用於查詢具有最大總和的連續子列表和

假設我們有一個數組 A。我們必須找到和最大的連續子列表，並返回其和。因此，如果陣列 A 為 A = [-2,1,-3,4,-1,2,1,-5,4]，則和將為 6。子陣列將為 [4, -1, 2, 1]。

為解決此問題，我們將嘗試使用動態規劃方法。

  • 定義一個數組 dp，大小與 A 相同，並用 0 填充

  • dp[0] := A[0]

  • i := 1 到 A 大小 – 1

    • dp[i] := dp[i – 1] + A[i] 和 A[i] 的最大值

  • 返回 dp 中的最大值

讓我們看看以下實現以獲得更好的理解 −

示例

即時演示

class Solution(object):
   def solve(self, nums):
      dp = [0 for i in range(len(nums))]
      dp[0] = nums[0]
      for i in range(1,len(nums)):
         dp[i] = max(dp[i-1]+nums[i],nums[i])
      return max(dp)
nums = [-2,1,-3,7,-2,2,1,-5,4]
ob1 = Solution()
print(ob1.solve(nums))

輸入

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

輸出

8

更新於： 09-Oct-2020

850 次瀏覽

開始你的職業生涯

透過完成課程獲取認證

入門
廣告