python求最大连续子数组的和

求解最大连续子数组的和是动态规划中的常见问题，在Python中可以用不同的算法来解决。具体流程和实现方法如下：

1. 定义状态：定义dp[i]表示以第i个元素结尾的最大连续子数组的和。
2. 定义状态转移方程：dp[i]的值可以通过如下公式递推得到：dp[i] = max(dp[i-1]+nums[i], nums[i])，其中nums是输入的数组。
3. 初始状态：dp[0]=nums[0]。
4. 最终的结果是数组dp中的最大值。

下面给出一个具体的实现示例：

def maxSubArray(nums: List[int]) -> int:
    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)

例如，对于数组[-2,1,-3,4,-1,2,1,-5,4]，使用上述算法可以得到最大连续子数组的和为6。

另外，上述算法还可以进行进一步的优化，即可以通过使用一个变量来记录当前最大的子数组和，在循环中更新该变量并动态维护最大值，从而节省空间。

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

例如，对于数组[-2,1,-3,4,-1,2,1,-5,4]，使用上述算法也可以得到最大连续子数组的和为6。