Longest Zigzag Subsequence
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
posts of different heights stand in a row in a park; the i-th post from the left has height nums[i].
You want to pick some posts (keeping their order; they need not be adjacent) to build a hopping course in which consecutive
heights always differ and the course alternates between going up and going down: for chosen heights the
signs of must strictly alternate (+ - + … or - + - …).
A single post, or two posts of different heights, also form a valid course. Return the maximum number of posts in a valid course.
Examples
| nums | result |
|---|---|
[1, 7, 4, 9, 2, 5] | 6 |
[1, 17, 5, 10, 13, 15, 10, 5, 16, 8] | 7 |
[3, 3, 3] | 1 |
Example 1 — The differences +6, -3, +5, -7, +3 already alternate.
Example 2 — For instance [1, 17, 10, 13, 10, 16, 8] has differences +16, -7, +3, -3, +6, -8.
Example 3 — All heights are equal, so no two posts can follow each other.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(nums: int[]) → int
Constraints
-
nums.length -
nums[i]
Expected complexity
- Time
- O(N)
- Space
- O(1)
Examples
| nums | Expected |
|---|---|
[1,7,4,9,2,5] | 6 |
[1,17,5,10,13,15,10,5,16,8] | 7 |
[3,3,3] | 1 |
Hint
Hint
The textbook DP up[i] = 1 + max(down[j]) over earlier smaller nums[j] is and times out. Only the previous element
matters: scan once keeping up and down (best length ending with a rise / a fall). If nums[i] > nums[i-1] set
up = down + 1; if nums[i] < nums[i-1] set down = up + 1; equal neighbours change nothing. Within a run of rises the
highest post is always the best one to keep. The answer is max(up, down), .
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1054 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 4 | verdict only |