376. Wiggle Subsequence

376. Wiggle Subsequence (Medium)

A sequence of numbers is called a wiggle sequence if 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.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Example 1:

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

Example 2:

Input: [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: [1,2,3,4,5,6,7,8,9]
Output: 2

Follow up:
Can you do it in O(n) time?

Related Topics:
Dynamic Programming, Greedy

Solution 1. DP

For each num[i], it is the last element of both 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) {
        if (nums.empty()) return 0;
        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);
    }
};