【LeetCode】53.最大子序和

题目地址：https://leetcode-cn.com/problems/maximum-subarray/submissions/

题目描述：

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

示例:

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

class Solution {
public:
    int maxSubArray(vector<int>& nums){
        if(nums.size()==1)return nums[0];
        int MaxSum = nums[0];
        int ThisSum = 0;
        for(int i=1;i<nums.size();i++){
            if(nums[i]>0)break;
            else if(MaxSum < nums[i])MaxSum = nums[i];
            if(i == nums.size() - 1) return MaxSum;//如果都是负数，返回最大的那个负数
        }
//代码核心，假设数组里含有正数
        MaxSum = 0;
        for(int i=0;i<nums.size();i++){
            ThisSum += nums[i];
            if(ThisSum > MaxSum)MaxSum = ThisSum;
            if(ThisSum < 0)ThisSum = 0;
        }
        return MaxSum;
    }
};

这种解法有点取巧，就是找规律，如果数组中含有正数，则最大的子序列头和尾都是正数（假设有多余两个正数，如果只有一个正数则最大子序列就是该正数），且最后结果肯定大于0，因此我们逐个求ThisSum,先保证子序列头是正数，然后如果发现ThisSum > MaxSum,则更新MaxSum,如果发现ThisSum < 0,则说明当前序列无法为后面提供最大子序列和，将ThisSum重置为0；如果都是负数则最大子序列是最大的那个负数。