python如何求数组连续最大和的示例代码

求一个数组的连续最大和可以采用动态规划的思想，下面是具体的攻略。

思路

设$dp[i]$表示以第$i$个数结尾的最大子段和，因此我们有了如下的动态转移方程：$$ dp[i] = \max(dp[i-1]+nums[i],nums[i]) $$ 其中变量$nums$为原始的数组，对于第一个数$nums[0]$，我们可以将其看做以第0个数结尾的最大子段和，因此$dp[0]$即为$nums[0]$。最终的连续最大和即为$\max\limits_{i=0}^{n-1}dp[i]$，其中$n$为数组的长度。

示例代码

下面是一个简单的Python示例代码：

def maxSubArray(nums: List[int]) -> int:
    if not nums:
        return 0
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    for i in range(1, n):
        dp[i] = max(dp[i-1]+nums[i], nums[i])
    return max(dp)

我们可以调用该函数，传入一个数组即可求出该数组的连续最大和：

nums = [-2,1,-3,4,-1,2,1,-5,4]
print(maxSubArray(nums))

运行结果为：6，说明原数组中最大的连续子数组为$[4,-1,2,1]$，其和为6。

示例说明

再举一个示例来说明该函数的使用方法。

nums = [1,2,-2,4,5,-3,2,3,-5]
print(maxSubArray(nums))

运行结果为：14，说明原数组中最大的连续子数组为$[1,2,-2,4,5,-3,2,3]$，其和为14。

上面的两个示例说明了该函数可以处理正、负数混合的情况，并且可以处理原数组中全部是负数的情况。