mediumGreedyPure DSA~20 min
Longest Wiggle Subsequence
A wiggle trend alternates strictly up and down. From a series of readings, find the length of the longest subsequence (not necessarily contiguous) whose successive differences alternate in sign.
Problem
Given an integer array nums, return the length of the longest wiggle subsequence: a subsequence whose successive differences strictly alternate between positive and negative. A single element and any two unequal elements are trivially wiggles.
Input
An integer array nums.
Output
An integer: the length of the longest wiggle subsequence.
Constraints
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 1000
Examples
Example 1
Input
nums = [1,7,4,9,2,5]
Output
6
The whole array already wiggles.
Example 2
Input
nums = [1,17,5,10,13,15,10,5,16,8]
Output
7
A length-7 wiggle subsequence exists.