Wiggle Subsequence
01 · Problem
A sequence is called a wiggle sequence if the differences between consecutive elements are all non-zero and strictly alternate between positive and negative. The first difference may be either positive or negative. A sequence with a single element counts as a wiggle sequence, and so does a two-element sequence whose elements differ.
A subsequence is formed by deleting zero or more elements from nums without changing the order of the rest.
Given an integer array nums, return the length of its longest wiggle subsequence. Note that equal adjacent values can never both appear consecutively in a wiggle sequence, so an array of identical values has answer 1.
02 · Examples
nums = [1,7,4,9,2,5]
6
The whole array wiggles: the differences are +6, -3, +5, -7, +3.
nums = [1,17,5,10,13,15,10,5,16,8]
7
One longest choice is [1,17,10,13,10,16,8] with differences +16, -7, +3, -3, +6, -8.
nums = [1,2,3,4,5,6,7,8,9]
2
The array only rises, so the best is any two different elements, such as [1,9].
03 · Constraints
- 011 <= nums.length <= 1000
- 020 <= nums[i] <= 1000
- 03Adjacent equal values may appear in nums and never count as a direction change
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.