Find the Longest Wiggle Subsequence Length
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Find the Longest Wiggle Subsequence Length
A wiggle sequence has successive differences that are nonzero and alternate between positive and negative. The first difference may have either sign. A sequence of one element is a wiggle sequence.
Given an integer array `nums`, return the length of its longest wiggle subsequence. A subsequence keeps the original relative order but may remove elements.
### Function
`int wiggleMaxLength(vector<int>& nums)`
### Example 1
```text
Input: nums = [1,4,4,2,5]
Output: 4
```
Selecting `[1,4,2,5]` gives differences `3,-2,3`. Selecting both consecutive copies of `4` would introduce a zero difference.
### Example 2
```text
Input: nums = [7,7,7]
Output: 1
```
### Example 3
```text
Input: nums = [2,5,8]
Output: 2
```
### Constraints
- `1 <= nums.length <= 1000`.
- `0 <= nums[i] <= 1000`.
### Clarifications
The result is a length, not the selected values. Elements need not be adjacent, but their order cannot change. Equal consecutive selected values do not form a valid difference.
### What a Strong Answer Covers
- The distinction between a subsequence and a contiguous subarray.
- Strict alternation and the treatment of equal values.
- Single-element, monotone, and repeated-value inputs.
- Why the reported length is optimal and the resource bounds.
### Follow-up
Can you solve the problem in `O(n)` time?
Overview: Practice finding the maximum length of an ordered wiggle subsequence. Handle strict sign alternation, equal values, monotone inputs, and a single element.
