Wiggle Subsequence

LeetCode Q 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.

Example 1:
Input: [1,7,4,9,2,5] ; Output: 6
Explanation: The entire sequence is a wiggle sequence.
Example 2:
Input: [1,17,5,10,13,15,10,5,16,8] ; Output: 7
Explanation: There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].
Example 3:
Input: [1,2,3,4,5,6,7,8,9] ; Output: 2

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

Solution :

Solution 1 : traditional DP

We use two arrays to store the states.

1. up[i]: the ith number is the peak.
2. sell[i]: the ith number is the vally.

We update these two arrays depends on the following case:

1. if (nums[i] > nums[i - 1]), which means the curr number is larger than its left, then we update up[i] = Math.max(up[i - 1], down[i - 1] + 1) and down[i] keeps the same (i.e. down[i] = down[i - 1]);
2. if (nums[i] < nums[i - 1]), which means the curr number is smaller than its left, then we update down[i] = Math.max(down[i - 1], up[i - 1] + 1) and up[i] keeps the same (i.e. up[i] = up[i - 1]);
3. if (nums[i] == nums[i - 1]), we will neither update up[i] nor sell[i], that is up[i] = up[i - 1] and down[i] = down[i - 1].

Time Complexity: O(n)
Space Complexity: O(n)

Code:

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

Solution 2 : DP Optimized Space

Using up and down instead of up[i] and down[i], optimizing the space complecity to be O(1).

Code:

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