Funcia
Lv.2dpgreedy

Longest Zigzag Subsequence

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

NN 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 h1,…,hkh_1, \dots, h_k the signs of h2−h1,h3−h2,…h_2 - h_1, h_3 - h_2, \dots 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

numsresult
[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

  • 1≤N=1 \le N = nums.length ≤200,000\le 200{,}000
  • −109≤-10^9 \le nums[i] ≤109\le 10^9

Expected complexity

Time
O(N)
Space
O(1)

Examples

numsExpected
[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 O(N2)O(N^2) 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), O(N)O(N).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251054 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.