天华建筑设计公司官网_电脑网络_搜索引擎优化面对哪些困境_长沙seo步骤

376. 摆动序列

使用动态规划来写，但是对动态规划的定义 导致算法复杂度不一样。
方法1：

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int n = nums.size();vector<int> dpBig(n,1);vector<int> dpSma(n,1);int ans = 1;for(int i=1;i<n;++i){for(int j=0;j<i;++j){if(nums[j]<nums[i]){dpBig[i] = max(dpBig[i],dpSma[j]+1);}if(nums[j] > nums[i]){dpSma[i] = max(dpSma[i],dpBig[j]+1);}}ans = max(ans,max(dpBig[i],dpSma[i]));}return ans;}
};

方法2：

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int n = nums.size();vector<int> up(n,1);vector<int> down(n,1);for(int i=1;i<n;++i){if(nums[i-1]>nums[i]){down[i] = max(down[i-1],up[i-1] + 1);up[i] = up[i-1];}else if(nums[i-1] < nums[i]){up[i] = max(up[i-1],down[i-1] + 1);down[i] = down[i-1];}else{up[i] = up[i-1];down[i] = down[i-1];}}return max(up[n-1],down[n-1]);}
};