Wiggle Subsequence

Problem

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:

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

Solution

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        int len = nums.length;
        if (len < 2) return len;
        int k = 1;
        while ( k < len && nums[k] == num[k-1]) k++;
        if (k == len) return 1; //All elements are same in nums 
        int result = 2;
        boolean needSmall = nums[k] > nums[k-1];
        for (int i = k; i < len - 1; i++) {
            if (needSmall && nums[i+1] < nums[i] || !needSmall && nums[i+1] > nums[i]) {
                nums[result++] = nums[i+1];
                needSmall = !needSmall;
            }  
        }
        return result;
    }
}

Analysis

The basic idea of this solution is that we assume the longest wiggle subsequence is from the first index. Then we compare the second one to first one to get the value of needSmall. We update the num[result++] if if follows wiggle pattern, otherwise, we just skip that number and continue the loop. The first if and while statement are to avoid some special cases (like they are all same).