O(n) solution c++ code


  • 0
    H

    This is basically a variation of 'longest increasing subsequence' problem. Refer to:
    https://en.wikipedia.org/wiki/Longest_increasing_subsequence

    The solution maintains 2 auxiliary arrays, s[i] stores the longest wiggle length up to index i; p[i] stores the wiggle link (precedent index link. it is not needed but I will just put it here as a pattern of solving similar problems.).

    int wiggleMaxLength(vector<int>& nums) {
    
        int len = nums.size();
        if (len < 2)
            return len ? 1 : 0;
    
        vector<int> s(len, 0);
        vector<int> p(len, 0);
    
        s[0] = 1; s[1] = nums[0] == nums[1] ? 1 : 2;
        p[0] = -1; p[1] = nums[0] == nums[1] ? -1 : 0;
        for (int i = 2; i < len; i++){
    
            if ((nums[i] > nums[i - 1] && nums[i - 1] < nums[p[i - 1]]
                || nums[i] < nums[i - 1] && nums[i - 1] > nums[p[i - 1]]))
                s[i] = s[i - 1] + 1, p[i] = i - 1;
            else
                s[i] = s[i - 1], p[i] = p[i - 1];
        }
    
        return s[len - 1];
    }

Log in to reply
 

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