376. Wiggle Subsequence - cocoder39/coco39_LC GitHub Wiki

376. Wiggle Subsequence

notes 2021:

  • step 1 - O(n^2) DP apprach
  • step 2 - optimize it to O(n) dp approach: rather than checking every element prior to i, we propagate the max to i-1
  • step 3 - memory optimization
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        up, down = [0] * n, [0] * n
        up[0], down[0] = 1, 1
        
        for i in range(1, n):
            if nums[i] > nums[i-1]:
                up[i] = down[i-1] + 1
                down[i] = down[i-1]
            elif nums[i] < nums[i-1]:
                up[i] = up[i-1]
                down[i] = up[i-1] + 1
            else:
                up[i] = up[i-1]
                down[i] = down[i-1]
        
        return max(up[-1], down[-1])

================================================================================

dp: O(n ^ 2) time and O(n) memory

int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() <= 1) { //0 or 1
            return nums.size();
        }
        
        vector<int> raise(nums.size(), 1); //raise[i] is max length of sequence raising at nums[i]
        vector<int> fall(nums.size(), 1); //fall[i] is max length of sequence falling at nums[i]
        int res = 0;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    raise[i] = max(raise[i], fall[j] + 1);
                }
                else if (nums[i] < nums[j]) {
                    fall[i] = max(fall[i], raise[j] + 1);
                }
            }
            res = max(res, max(raise[i], fall[i]));
        }
        return res;
    }

solution 2 : O(n) time and memory can be optimized to O(1)

int wiggleMaxLength(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        vector<int> fall(nums.size());
        vector<int> raise(nums.size());
        raise[0] = 1, fall[0] = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > nums[i - 1]) {
                raise[i] = fall[i - 1] + 1;
                fall[i] = fall[i - 1];
            }
            else if (nums[i] < nums[i - 1]) {
                fall[i] = raise[i - 1] + 1;
                raise[i] = raise[i - 1];
            }
            else {
                raise[i] = raise[i - 1];
                fall[i] = fall[i - 1];
            }
        }
        return max(raise[nums.size() - 1], fall[nums.size() - 1]);
    }

int wiggleMaxLength(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        
        int fall = 1, raise = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > nums[i - 1]) {
                raise = fall + 1;
            }
            else if (nums[i] < nums[i - 1]) {
                fall = raise + 1;
            }
        }
        return max(raise, fall);
    }
⚠️ **GitHub.com Fallback** ⚠️