最大子序和

题目描述

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

示例:

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

题目链接：https://leetcode.cn/problems/maximum-subarray/

文章讲解：https://programmercarl.com/0053.最大子序和.html

思考

贪心解法

暴力解法是双层循环，第一层 for 就是设置起始位置，第二层 for 循环遍历数组寻找最大值。

这个思路是可以优化的。

例如【-2，1，-3，4，-1，2，1，-7，4】

对于这个数组，外层 for 循环 -2 内层1往后。我们找-2开头的子数组。

然后外层for循环从1开始，内层-3往后，找1开头的子数组。

我们发现**-2开头的数组中的子数组和一定要比1开头的数组中的子数组和小**。

为什么会这样，因为 -2 加后面的任何子数组都会使其变小。

这样我们就知道了那外层的-2的这层循环不用进行了，相当于我们提前终止了外层for循环。

所以，规律是什么？

我们先计算从-2开始的子数组和，经过以上分析，排除-2，继续从1开始，【1，-3】，我们发现这时和为-2。又遇到了之前的问题。之后是【1，-3，4...】既然前两个和为-2了，为什么我不舍弃前两个，直接从4开始计数呢？因为只要带上前两个就是“累赘”，我该抛弃它们。

思路就是，从第一个元素开始，计算连续和，这个连续和会不断更新我们要的最大连续子数组和，如果连续和小于0了，意味着应该重新开始计算连续和。

代码实现

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT_MIN;
        int count = 0;
        for(int i = 0;i < nums.size();i++){
            count += nums[i];
            result = result > count ? result : count;
            if(count <= 0) count = 0;
        }
        return result;
    }
};