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

发布时间:2023年12月18日

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从下一位开始重新累加。

文章来源:https://blog.csdn.net/weixin_58515995/article/details/134991914
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。