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:

1
2
3
4
5
6
7
8
9
10
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?

思路

利用贪心的方法可以做。

譬如[1,7,4,9,2,5]这个数组，差值数组为[6,-3,5,-7,3]。 如果差值是[6,3,5,6,1,6,-3,-1,5,7,3]，我们就可以把前面的六个正数看成一个正数，两个负数看成一个负数，以此类推，统计最终合并后的元素个数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length < 2) return nums.length;
        else{
            int[] remember = new int[nums.length - 1];
            for(int i = 0; i < nums.length - 1; i++){
                remember[i] = nums[i+1] - nums[i];
            }
            int k = 0;
            while(k < remember.length && remember[k] == 0) k++;
            boolean positive = true;
            if(k < remember.length){
                positive = true;
                if(remember[k] < 0) positive = false;
            }
            else return 1;
            int count = 0;
            while(k < remember.length){
                count++;
                if(positive){
                    while(k < remember.length && remember[k] >= 0) k++;
                    positive = false;
                }
                else{
                    while(k < remember.length && remember[k] <= 0) k++;
                    positive = true;
                }
            }
            return count+1;
        }
    }
}