376. Wiggle Subsequence #

Problem #

Given an integer array nums, return the length of the longest wiggle sequence.

A wiggle sequence is a sequence where 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.

A subsequence is obtained by deleting some elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Example 1:

Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence.

Example 2:

Input: nums = [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: nums = [1,2,3,4,5,6,7,8,9]
Output: 2

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

Follow up: Could you solve this in O(n) time?

Problem Summary #

If the differences between consecutive numbers strictly alternate between positive and negative, the sequence is called a wiggle sequence. The first difference (if it exists) may be either positive or negative. A sequence with fewer than two elements is also a wiggle sequence. For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) alternate between 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 both positive, and the second because its last difference is zero. Given an integer sequence, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some elements (or none) from the original sequence, with the remaining elements keeping their original order.

Solution Approach #

• The problem requires finding the longest subsequence that is a wiggle sequence. This problem can be solved with a greedy approach by recording the current sequence’s upward and downward trends. While scanning the array, determine whether each element is a “peak” or a “valley”, and make the corresponding decision based on whether the previous one was a “peak” or a “valley”. Use the greedy idea to find the longest wiggle subsequence.

Code #

package leetcode

func wiggleMaxLength(nums []int) int {
	if len(nums) < 2 {
		return len(nums)
	}
	res := 1
	prevDiff := nums[1] - nums[0]
	if prevDiff != 0 {
		res = 2
	}
	for i := 2; i < len(nums); i++ {
		diff := nums[i] - nums[i-1]
		if diff > 0 && prevDiff <= 0 || diff < 0 && prevDiff >= 0 {
			res++
			prevDiff = diff
		}
	}
	return res
}