# C++ DP solution with detailed explaination

• ``````/* 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.
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];
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.