376. Wiggle Subsequence - jiejackyzhang/leetcode-note GitHub Wiki

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.

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

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

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

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

解题思路为Dynamic Programming。

##Approach 1: Dynamic Programming O(n^2) 用两个数组分别记录以该元素为结尾时的length，分别为difference为positive和negative。 时间复杂度为O(n^2)，空间复杂度为O(n)。

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int len = nums.length;
        int[] p = new int[len];
        int[] n = new int[len];
        p[0] = 1;
        n[0] = 1;
        for(int i = 1; i < len; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) {
                    p[i] = Math.max(p[i], n[j]+1);
                } else if(nums[j] > nums[i]) {
                    n[i] = Math.max(n[i], p[j]+1);
                } else {
                    p[i] = Math.max(p[i], p[j]);
                    n[i] = Math.max(n[i], n[j]);
                }
            }
        }
        return Math.max(p[len-1], n[len-1]);
    }
}

##Approach 2: Linear Dynamic Programming O(n)

1. 若nums[i] > nums[i-1]，则p[i]=n[i-1]+1，n[i]=n[i-1]；
2. 若nums[i] < nums[i-1]，则p[i]=p[i-1]，n[i]=p[i-1]+1；
3. 若nums[i] == nums[i-1]，则p[i]=p[i-1]，n[i]=n[i-1]。

时间复杂度为O(n)，空间复杂度为O(n)。

注意到p[i]，n[i]均只需要i-1时刻的值，因此无需使用数组，只需设置一个变量即可。空间复杂度优化为O(1)。

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums == null) return 0;
        int len = nums.length;
        if(len < 2) return len;
        int p = 1, n = 1;
        for(int i = 1; i < len; i++) {
            if(nums[i] > nums[i-1]) {
                p = n + 1;
            } else if(nums[i] < nums[i-1]) {
                n = p + 1;
            } 
        }
        return Math.max(p, n);
    }
}