Python实现最大连续子数组和算法

可以使用动态规划的思想来解决这个问题。假设当前位置为i，那么以i结尾的子数组的最大和可以分为两种情况：

1. 以i-1结尾的子数组的最大和加上nums[i]，即dp[i-1]+nums[i]
2. 只包含nums[i]，即nums[i]

那么以i结尾的子数组的最大和就是这两种情况中的最大值。因此，可以用一个数组dp来记录以每个位置为结尾的子数组的最大和，最终返回dp中的最大值即可。

代码如下：

def maxSubArray(nums):
    dp = [0] * len(nums)
    dp[0] = nums[0]
    max_sum = dp[0]
    for i in range(1, len(nums)):
        dp[i] = max(dp[i-1] + nums[i], nums[i])
        max_sum = max(max_sum, dp[i])
    return max_sum

测试代码：

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArray(nums))  # 输出6