```
/* Optimal substructure:
WS[i] = 1 + max(WS[j]), 0 < j < i and n[i] - n[j] and posFront[j] must be opposite.
If no such j found, ith index will end up making 2 length WS with first element, i.e. 0th.
The main concept is similar to LIS, additionally we need to keep sign information of last
subproblem as next item will join seq with opposite sign subproblem front.
Overlapping subproblems:
Used memoization to prevent recomputation each time ith index looks back to join the
sequence
*/
class Solution {
public:
int wiggleMaxLength(vector<int>& n) {
if (n.size() == 0) return 0;
vector<int> len(n.size());
vector<bool> posFront(n.size(), true);
len[0] = 1;
for (int i = 1; i < n.size(); i++) {
for (int j = i - 1; j >= 0; j--) {
if (j == 0) {
len[i] = n[i] == n[j] ? len[j] : len[j] + 1;
posFront[i] = n[i] < n[j] ? false : true;
}
else if (posFront[j] && n[i] - n[j] < 0) {
posFront[i] = false;
len[i] = len[j] + 1;
break;
}
else if (!posFront[j] && n[i] - n[j] > 0) {
posFront[i] = true;
len[i] = len[j] + 1;
break;
}
}
}
return len[n.size()-1];
}
};
```