题目描述

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

子数组 是数组中的一个连续部分。

示例

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

1 <= nums.length <= 10510^{5}105
−104-10^{4}−104 <= nums[i] <= 10410^{4}104

题目分析

这道题和之前解答过的 水桶最多能盛多少水 有点像，水桶盛水最多的问题使用双指针是最优解。

这道题经过测试和演算，发现动态规划的思路是最优解：

我们可以把解题思路拆分为，每个节点都和上一个节点比较，即：是当前节点的值大？还是当前节点+前一个节点的值大？

把问题进行拆分，一直进行这种比较，最终获得最大的值。

思路讲解

1. 初始化最大值max，因为从头开始，默认最大值就是数组下标为0时对应的值。
2. 进行循环遍历，遍历数组长度的次数
3. 在for循环中进行题目分析中的逻辑判断：
4. 如果当前节点的值+前一个节点的值>当前节点的值：我们更新当前节点的值为前一个节点值+当前节点值。
5. 在for循环中进行判断，如果相加后的当前节点值大于目前的最大值max，就更新max
6. 一直进行循环判断直到结束
7. 返回max即可，就是我们需要的最大子数组和

AC代码

func maxSubArray(nums []int) int {
    max := nums[0]
    for i := 1; i < len(nums); i++ {
        if nums[i] + nums[i-1] > nums[i] {
            nums[i] += nums[i-1]
        }
        if nums[i] > max {
            max = nums[i]
        }
    }
    return max
}

运行结果

总结

复杂度

时间复杂度：O(n)，其中n是输入数组的长度。

空间复杂度：O(1)，因为我们只需要常数空间来存放变量就可以了。