用 Python 编写程序，查找具有最大和的连续子列表的总和

pythonserver side programmingprogramming更新于 2026/1/18 0:12:17

假设我们有一个数组 A。我们必须找到具有最大和的连续子列表，并返回其和。因此，如果数组 A 类似于 A = [-2,1,-3,4,-1,2,1,-5,4]，则和将为 6。子数组将为 [4, -1, 2, 1]。

为了解决这个问题，我们将尝试使用动态规划方法。

定义一个与 A 大小相同的数组 dp，并用 0 填充它
dp[0] := A[0]
for i := 1 to size of 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))