**Observations:**

- If there are more than two (assuming
*n*) continuous positives in the difference sequence, which means the subsequence is monoly increasing, we can keep only one. Same for the case of more than two continuous negatives. - If there is a zero in the difference sequence, we can simply just remove it since it won't change the increasing or decreasing state but will certainly change the length of a subsequence of continuous positives or negatives

**Algorithm:**

- Calculate the difference sequence
- Traverse the difference sequence and combine continuous positives into one positive (if 0 is in the middle, simply ignore it). Do the same combination for continuous negative until the end.
- Count the remaining numbers n in the combined sequence, the length of the longest subsequence is simply
*n+1*

**Complexity**

Time required is *2*(n-1)* where n is the list length, so time complexity is ** O(n)**, i.e. linear time

```
int getSign(const int& v)
{
if (v > 0) return 1;
if (v < 0) return -1;
return 0;
}
int wiggleMaxLength(vector<int>& nums)
{
int len = nums.size();
if (len == 0) return 0;
if (len == 1) return 1;
if (len == 2) {
if (nums[0] == nums[1]) return 1;
else return 2;
}
//compute the difference sequence
int i;
vector<int> d;
for (i = 1; i < len; ++i) {
d.push_back(nums[i] - nums[i - 1]);
}
//now virtually combine the continuous positives and negatives together
//find the first non-zero value in the difference sequence
for (i = 0; i < len - 1; i++) {
if (d[i] != 0) break;
}
if (i == len - 1) return 1; //the whole sequence contains one single number
int count = 1;
int preSign = getSign(d[i]);
for (int j = i + 1; j < len - 1; ++j) {
int curSign = getSign(d[j]);
if (curSign != 0 && curSign != preSign){
count++;
preSign = curSign;
}
}
return count + 1;
}
```