12.14 log 376. 摆动序列，53. 最大子序和

376. 摆动序列

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size()==1) return nums.size();
        int preDiff=0;
        int curDiff=0;
        int result=1;
        for(int i=0;i<nums.size()-1;i++){
            curDiff=nums[i+1]-nums[i];
            if(preDiff<=0&&curDiff>0||preDiff>=0&&curDiff<0){
                preDiff=curDiff;
                result++; 
            }
        } 
        return result;
    }
};

局部最优就是看波峰波谷，全局最优就是求出波峰波谷的总和，求波峰波谷的涉及到平峰，涉及到首位两端，如果传入的数组长度为1，则直接返回1，我们只考虑数组长度大于1的情况，考虑首位两端的情况时，初始位置的前一位preDiff初始值设置为0，意思是假定初始位置前面是平峰，遍历的数组长度设置size-1，因为result的初始值已经为1了 ，当遍历到末尾时实际上已经是result+1了，这种情况还可以避免curDiff数据溢出，遇到平峰时，我们考虑左侧为平的情况因为preDiff我们初始值为0，默认左侧为平峰，为了避免单调平峰，我们的preDiff在有波动的时候变化，可以避免单调性相同重复记录的情况。

53. 最大子序和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum=0;
        vector<int> result;
         for(int i=0;i<nums.size();i++){
            sum+=nums[i];
            result.push_back(sum);
            if(sum<0){
                sum=0;
                continue;
            } 
        }
        sort(result.begin(),result.end());
        return result.back();
    }
};

贪心贪的就是结果越加越大，前面累加结果为负数时直接抛弃，sum从零开始重新累加，所有累加的结果都要记录进vector数组，最后排序，返回最大值。

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=count>result?count:result;
            if(count<0) count=0;
        }
        return result; 
    }
};

这个版本省略了vector数组，用整型result来记录累加的最大值，count来累加，一旦数组累加值为负时，该数组对后序数组的累加值毫无贡献，摒弃当前数组，count清零，但是result并不会清零，会记录之前的正向累加值，count从下一位开始重新累加。