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 次浏览

开始你的职业生涯

通过完成课程获取认证

入门
广告