# Wiggle Subsequence Solutions in C++

Number 376

Difficulty Medium

Acceptance 39.7%

Link LeetCode

Other languages —

## Solutions

### C++ solution by haoel/leetcode

// Source : https://leetcode.com/problems/wiggle-subsequence/// Author : Calinescu Valentin// Date : 2016-08-08/* Solution* --------* 1) O(N)** We notice that adding a new number to an existing subsequence means finding one that* is smaller or bigger than the previous number, according to the difference between the* previous number and the number before that as we always need to alternate between increasing* and decreasing subsequences. If we encounter increasing or decreasing sequences of 2 or* more consecutive numbers we can treat the entire subsequence as a number, because that way* we can always be sure we don't miss any solution, as finding a number smaller than any* number of an increasing subsequence is guaranteed to be smaller than the biggest number* in the subsequence. Thus, we can only check the difference between consecutive numbers.** Follow up:** The time complexity is already O(N).*/class Solution {public:int wiggleMaxLength(vector<int>& nums) {int solution = 0;//if we have an empty vector the solution is 0if(nums.size()){solution = 1;int bigger = 0;//0 is the starting point to be followed by either an increasing or decreasing sequencefor(int i = 1; i < nums.size(); i++){if(nums[i] == nums[i - 1])continue;//we can ignore duplicates as they can always be omittedelse if(nums[i] > nums[i - 1]){if(bigger == 0 || bigger == 2){bigger = 1;//1 means we now have an increasing sequencesolution++;}}else //if(nums[i] < nums[i - 1]){if(bigger == 0 || bigger == 1){bigger = 2;//2 means we now have a decreasing sequencesolution++;}}}}return solution;}};