C++ DP solution with detailed explaination


  • 0
    V
    /* 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];
        }
    };
    

Log in to reply
 

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