Wiggle Subsequence

https://leetcode.com/problems/wiggle-subsequence/description/

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.

Thoughts

数组求某种子序列长度想DP. 先想到f[i]表示以nums[i]为结尾的最长wiggle序列，但发现只有一个数并不行，因为假如以它结尾最长的最后是+, 但不代表全局最优nums[i]就是+. 因此维持两种序列的结果。

Code

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[][] f = new int[n][2];

        int max = 1;
        for (int i = 0; i < n; i++) {
            f[i][0] = 1;
            f[i][1] = 1;
            for (int j = 0; j <= i; j++) {
                if (nums[i] - nums[j] > 0) {
                    f[i][0] = Math.max(f[i][0], f[j][1] + 1);
                } else if (nums[i] - nums[j] < 0) {
                    f[i][1] = Math.max(f[i][1], f[j][0] + 1);
                }
            }
            max = Math.max(max, Math.max(f[i][0], f[i][1]));
        }

        return max;
    }
}

Analysis

做题耗时17min.

时间复杂度是O(n^2).

Ver.2

把整个nums画出来, 是个大的波浪. 无论在波浪上怎么取, 都没有在拐点处取生成的摇摆序列长.

摇摆序列要求升高，降低，升高。。。

或者降低，升高，降低。。。

那么我们只要找出数组中的“拐点” 即可 举个例子:

4 5 6 3 2 1这几个数中，4为起点，那么5和6中，我们肯定选6啊~因为之后的数要求小于5，小于5的必定也小于6 比如改为4 5 6 5，之前要是选5就没办法继续往下了。。

总之就是选最小的和选最大的（也就是拐点） 保证不丢最优解。

First we check if the series is starting as (big, small) or (small, big). So as 2,1 is big, small. So we will start the loop as we need small number first that is 1 as 2 is already there.

Step 1: First we check our requirement is to get small number. As 1<2 so the series will be

2,1

Step 2: Now we need big number that is greater than 1. As 4>1 so series will be

2,1,4

Step 3: Now we need small number. But 5>4 so 4 will be replaced by 5. So the series will become

2,1,5

Step 4: We need small number. But 6>5. Series will be

2,1,6

Step 5: Require small number. 3<6. Series will be

2,1,6,3

Step 6: Require big number. 3=3. No change in series

2,1,6,3

Step 7: Require big number. 4>3. Series will become

2,1,6,3,4

Step 8: Require small number. 8>4. 8 will replace 4 and series will become

2,1,6,3,8

Step 9: Require small number. 4<8. So final series will be

2,1,6,3,8,4

Answer is 6.

public int wiggleMaxLength(int[] nums) {
    if (nums.length <= 1) return nums.length;

    int count = nums.length;
    Boolean positive = null;

    for (int i = 0; i < nums.length-1; i++){
        int temp = nums[i+1] - nums[i];
        if (temp == 0) count--;
        else if (positive == null) positive = temp > 0;
        else if ((temp > 0 && positive) || (temp < 0 && !positive))
            count--;
        else
            positive = !positive;
    }
    return count;
}