给定一个整数数组 nums ,找到一个具 有最大和的连续子数组(子数组最少包 含一个元素),返回其最大和。

这是一个经典的动态规划问题，可以使用 Kadane's Algorithm 来解决。具体来说，我们可以使用一个变量 maxSum 来记录当前最大的子数组和，使用另一个变量 curSum 来记录当前的子数组和。遍历整个数组，对于每个元素，我们可以将其加入当前的子数组中，然后更新 curSum。如果 curSum 大于 maxSum，我们就更新 maxSum 的值。如果 curSum 变成了负数，我们就将其重置为 0，表示当前的子数组不能再向后扩展，需要从下一个元素重新开始构建子数组。

具体实现可以参考以下代码：

int maxSubArray(vector<int>& nums) {
    int maxSum = INT_MIN, curSum = 0;
    for (int num : nums) {
        curSum += num;
        maxSum = max(maxSum, curSum);
        curSum = max(curSum, 0);
    }
    return maxSum;
}

该算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

相关问题

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

思路：动态规划

1. 定义状态：dp[i]表示以第i个数结尾的最大子数组和

2. 状态转移方程：dp[i] = max(nums[i], dp[i-1]+nums[i])

3. 初始状态：dp[0] = nums[0]

4. 最终结果：遍历dp数组，求出最大值即可

Python代码：

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

时间复杂度：O(n)

空间复杂度：O(n)

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 用c++

语言实现的代码如下：

#include <stdio.h>
#include <limits.h>

int maxSubArray(int* nums, int numsSize){
    int maxSum = INT_MIN, curSum = 0;
    for(int i = 0; i < numsSize; i++){
        curSum += nums[i];
        if(curSum > maxSum){
            maxSum = curSum;
        }
        if(curSum < 0){
            curSum = 0;
        }
    }
    return maxSum;
}

int main(){
    int nums[] = {-2,1,-3,4,-1,2,1,-5,4};
    int numsSize = sizeof(nums) / sizeof(int);
    int maxSum = maxSubArray(nums, numsSize);
    printf("The maximum sum of contiguous subarray is %d\n", maxSum);
    return 0;
}

解释：使用Kadane算法，初始化当前和curSum为0，最大和maxSum为INT_MIN。遍历数组，对于每个元素，将其加到curSum中，如果curSum大于maxSum，则更新maxSum。如果curSum小于0，则将其重置为0。最后返回maxSum即可。