💫53.最大子序和

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

示例:

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

思路

基本想法

遍历容器，如果当前的元素大于零，就加到后面的元素中，然后记录相加之后的结果

如果相加小于零，说明会拉低连续子序列的大小，就不加到当前位置，但是需要尝试当前位置加到后面的序列中是不是正数

进行一遍遍历之后，最大的子序列一定会出现在容器的某个位置中，找出最大值即可

找最大值还需要排序之后找出容器开头或末尾的元素，消耗时间。

可以找一个标志记录每次都最大值，有最大值就更新，这样运行结束之后标志中就存放着最大值

一定要从大于零的位置开始累加，因为[-1,2,4,3,-1,7]和[2,4,3,-1,7]相比，肯定是从正数元素开始累加才会更大

总结：一旦出现负值，就需要放弃之前的累加，重新从当前的正值元素开始累加

执行流程

遍历容器，从前向后累加元素，一旦出现小于零的累加，就放弃这段序列，重新从大于零的位置开始累加，原因参考[-1,2,4,3,-1,7]和[2,4,3,-1,7]，在累加的过程中，每走一步统计一下最大值，判断是否更新

而只要累加之后是正数，就可以对序列和起到增益效果

每一步累加之后都需要先统计是否更新最大值，之后再将负数截断，因为最大子序和可能是一个负数

这样即使出现最大值，然后后面出现一个负数将最大值拉低，那么也会记录这个最大值，代码搜索的过程如下：

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //记录最大值的标志
        int res=INT32_MIN;
        //记录序列的累加和
        int sum=0;
        //遍历容器
        for(int i=0;i<nums.size();++i){
            sum+=nums[i];
            //每走一步就统计一下最大值
            //并且必须放在累加之后，因为有可能最大序列和是负数
            //此时就会
            if(sum>res)
                res=sum;
            //小于零的序列和舍弃
            if(sum<0)
                sum=0;
        }
        return res;
    }
};

总结

遍历容器，然后一步一步的累加，判断是否比最大值大，大的话就更新，之后判断如果子序和如果是负数的话就截断，因为只有正数才会对子序和产生增益效果

由于最大子序和有可能是负数，所以截断的操作必须放在统计最大值之后

并且每一步都会统计，所以即使最大值被负数拉低，程序中也有记录

尽可能的往后加，相加得出负数才会放弃当前子序列，因为负数对累加无法起到增益效果

程序运行结束，得到最大子序和

不能让“连续和”为负数的时候加上下一个元素，而不是 不让“连续和”加上一个负数