376

376. Wiggle Subsequence (Medium)

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?

Related Topics:
Dynamic Programming, Greedy

Solution 1. DP

num[i] is the last element of the following two sequences:

1. a sequence whose last two elements are decreasing. Let it be dec[i].
2. a sequence whose last two elements are increasing. Let it be inc[i].

If nums[i - 1] < nums[i] (i.e. increasing), we can do the following updates:

1. update inc[i] to be dec[i - 1].append(nums[i])
2. update dec[i] to be dec[i - 1]. Keeping the dec sequence unchanged will make it more likely to find the next increasing element.

If nums[i - 1] > nums[i] (i.e. decreasing), we can do the following updates:

1. update inc[i] to be inc[i - 1].
2. update dec[i] to be inc[i - 1].append(nums[i]).

If nums[i - 1] == nums[i], we can simply ignore nums[i].

In this way we can form the best solution.

Since here we only need to keep track of the length of inc[i] and dec[i], we just + 1 instead of append(nums[i]) in the above equations.

// OJ: https://leetcode.com/problems/wiggle-subsequence/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int inc = 1, dec = 1, N = nums.size();
        for (int i = 1; i < N; ++i) {
            if (nums[i] > nums[i - 1]) inc = dec + 1;
            else if (nums[i] < nums[i - 1]) dec = inc + 1;
        }
        return max(inc, dec);
    }
};

Solution 2. Greedy

If A[i] == A[i - 1], we skip it.

If A[i] is extending the previous trend, we can skip it.

Otherwise, we can increase the length of the subsequence and use the new trend.

class Solution {
public:
    int wiggleMaxLength(vector<int>& A) {
        int dir = 0, len = 1;
        for (int i = 1; i < A.size(); ++i) {
            int d = A[i] - A[i - 1];
            d = d > 0 ? 1 : (d < 0 ? -1 : 0);
            if (d != 0 && d != dir) {
                ++len;
                dir = d;
            }
        }
        return len;
    }
};