连续子数组最大的和

Question

连续子数组最大的和可以使用动态规划来求解。

假设 dp[i]表示以第 i 个元素结尾的连续子数组的最大和。那么我们可以得到以下递推关系：

• 如果 dp[i-1]大于 0，那么 dp[i] = dp[i-1] + nums[i]；
• 如果 dp[i-1]小于等于 0，那么 dp[i] = nums[i]。

我们可以使用一个变量 maxSum 来记录连续子数组的最大和，每次更新 maxSum 的值，即可得到最终结果。

以下是解决这个问题的 Python 代码：

def maxSubArray(nums):
    if not nums:
        return 0

    maxSum = nums[0]
    dp = [0] * len(nums)
    dp[0] = nums[0]

    for i in range(1, len(nums)):
        if dp[i-1] > 0:
            dp[i] = dp[i-1] + nums[i]
        else:
            dp[i] = nums[i]

        maxSum = max(maxSum, dp[i])

    return maxSum

该算法的时间复杂度为 O(n)，其中 n 为数组的长度。