LeetCode Wiggle Subsequence

· 769 words · 2 minute read
2017年6月
LeetCode-动态规划 · LeetCode-贪心

376. Wiggle Subsequence

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

方法1–动态规划

实际上这道题有点类似于博弈论那题，对于动态规划题目不再只是生成一个普通二维数组，而是根据点的不同状态生成对应状态的数组，当然状态可以由二维数组中的其中一维表示。

实际上对于在数组里的每一个点，它都有3种状态

  1. 上升状态，num[i] > num[i-1]，之前的num[i-1]必定在下降状态，num[i]的下降状态等于num[i-1]的下降状态
  2. 下降状态，num[i] < num[i-1]，理由同上。
  3. 和相等状态，num[i] == num[i-1]

例如：1,17,5,10,13,15,10,对于最后一个10,它可以看做对于前面13或15的下降，也可以看做对于前面5的上升。

所以要使用两个数组来分别记录对于一个点的上升状态和下降状态，然后对于最后一个点求两个状态的最大值。

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        int[] down = new int[nums.length];
        int[] up = new int[nums.length];
        down[0] = 1;
        up[0] = 1;

        for(int i = 1; i < nums.length; i++){
            if(nums[i]-nums[i-1] > 0){
                up[i] = down[i-1] + 1;
                down[i] = down[i-1];
            }else if(nums[i] - nums[i-1] < 0){
                down[i] = up[i-1] + 1;
                up[i] = up[i-1];
            }else{
                down[i] = down[i-1];
                up[i] = up[i-1];
            }
        }
        return Math.max(down[nums.length-1],up[nums.length-1]);
    }
}

方法2–贪心

本人数学功底较差，无法证明为何贪心也能取得最优解，只是在网上看了一下贪心的方法，觉得也挺有道理的。

举例如下：

数组： 1,17,5,10,13,15,10,5,16,8

相对应最长摇摆序列的长度：1,2, 3, 4, 4, 4, 5, 5,6,7

对于递增数组，取递增数组后的最后一个。对于递减数组，取递减数组后的最后一个，这样才能尽可能的包含最多的情况，所以相对应选择15和5。 如何证明，大家可以看看LeetCode上的证明，代码本人也就不贴了哈。

Share