python每日一题：连续子数组的最大和

这是一道关于动态规划的算法题：

题目描述：
给定一个整数数组 nums，请找出该数组中连续子数组的最大和，并返回这个最大和。

示例：
输入：[-2, 1, -3, 4, -1, 2, 1, -5, 4]
输出：6
解释：连续子数组 [4, -1, 2, 1] 的和最大，为 6。

编写一个函数 maxSubArray(nums) 来解决这个问题，函数的输入参数 nums 是一个整数数组，返回值为最大和。

要求使用动态规划的思想来解决这个问题。

提示：

• 可以假设输入的数组至少包含一个元素。

请尝试解答这道题，如果有任何疑问，请随时提问。

def maxSubArray(nums):
    n =len(nums)
    dp = n * [0]
    dp[0] = nums[0]
    max_sum = dp[0]
    for i in range(1,n):
        dp[i] = max(dp[i-1]+nums[i],nums[i])
        max_sum = max(max_sum,dp[i])
    print(max_sum)
nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4]
maxSubArray(nums)

dp[i-1] 的含义。在遍历数组 nums 的过程中，我们计算 dp[i] 的值，表示以 nums[i] 结尾的连续子数组的最大和。在计算 dp[i] 时，我们需要考虑两种情况：

nums[i] 单独构成一个子数组，此时 dp[i] = nums[i]。
将 nums[i] 与前面的连续子数组相连，此时 dp[i] = dp[i-1] + nums[i]。
我们需要选择使 dp[i] 达到最大的方式，因此我们比较这两种情况的结果，取较大的值作为 dp[i] 的值。

通过这种方式，我们不断更新 dp 数组的值，最终得到以每个位置 i 结尾的连续子数组的最大和。遍历完整个数组后，最大的 dp[i] 值即为所求的最大和。