程序在Python中查找具有最大和的连续子列表的和

2026-06-05 1 花语

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

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

定义一个与A大小相同的数组dp，并用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]

输出结果