0376. Wiggle Subsequence

Given an integer array nums, return the length of the longest wiggle sequence**.

A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

• For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) are alternately positive and negative.
• In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

A subsequence is obtained by deleting some elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Example 1:

Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence.

Example 2:

Input: nums = [1,17,5,10,13,15,10,5,16,8]
Output: 7
Explanation: There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Example 3:

Input: nums = [1,2,3,4,5,6,7,8,9]
Output: 2

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

Follow up: Could you solve this in O(n) time?

Analysis

The brute force solution is using the "choose or not" method to check for each element from the array, and it takes $O(n)$ for each result validation (check if it is indeed a wiggle sequence), and the total time complexity is $O(n! \times n)$. It will result in TLE.

Dynamic Programming: Another approach is using two arrays to record the current status' longest subsequence count (with the last element being nums[i]). For each point, we could choose either to append the previous "rising" subsequence or "falling" subsequence — thus we need two arrays. The time complexity for this approach is $O(n^2)$, and the space complexity is $O(2 \times n)$.

Dynamic Programming Improved: If we think carefully, there is some correlation between our two arrays. If we mark one array as up[i] and another one as down[i], we can find that if nums[i] > nums[i-1] (going up), the previous one must be going down, and we will have the maximum value from down[i - 1], since down[i - 1] >= down[i - 2] … >= down[0]. The same logic applies to nums[i] < nums[i - 1]. Using this method, we don't need to iterate through nums twice, but just a linear scan should be able to solve this problem. To further improve, since we are only interested in the previous down or up, we don't need to store all the results from down[0] … down[i-1], so we can minimize these arrays into two variables. Time complexity will be $O(n)$ and space is $O(1)$.

Code: brute force

class Solution {
public:
    int dfs(vector<int>& a, int idx, bool status) {
        int cnt = 0;
        // start checking from current index + 1
        for (int i = idx + 1; i < a.size(); ++i) {
            // a[prev] < a[i]
            if ((status && a[i] > a[idx]) || (
            // a[prev] > a[i]
              !status && a[i] < a[idx])) {              
                cnt = max(cnt, 1 + dfs(a, i, !status)); // each iteration will change the direction
            }
        }
        return cnt;
    }
    int wiggleMaxLength(vector<int>& a) {
        if (a.size() < 2) return a.size();
        return 1 + max(dfs(a, 0, false), dfs(a, 0, true));
    }
};

Code: DP with two arrays

class Solution {
public:
    int wiggleMaxLength(vector<int>& a) {
        int n = a.size();
        if (n < 2) return n;
        vector<int> up(n), down(n);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (a[i] < a[j]) { // now: up, prev: down
                    down[i] = max(down[i], up[j] + 1);
                } else if (a[i] > a[j]) { // now: down, prev: up
                    up[i] = max(up[i], down[j] + 1);
                }
            }
        }
        return max(up.back(), down.back()) + 1;
    }
};

Code: DP with two variables

class Solution {
public:
    int wiggleMaxLength(vector<int>& a) {
        int n = a.size();
        if (n < 2) return n;
        int up = 1, down = 1;
        for (int i = 1; i < n; ++i) {
            if (a[i] < a[i - 1]) // now: up, prev: down
              /*
                up = max(up, down + 1);
                                we can actually ignore up, since prev has to be down and if we don't choose, our down variable isn't changed
                                */
              up = down + 1;
            else if (a[i] > a[i - 1])
              /*
                down = max(down, up + 1);
                same logic here
              */
              down = up + 1;
        }
        return max(up, down);
    }
};