583. Up-Down Subsequence
A fitness band stores the number of steps taken each day in nums. A coach wants to highlight as many days as possible while keeping their original order, so that the day-to-day changes between consecutive highlighted days strictly alternate in direction: up, down, up, ... or down, up, down, ... A change of zero (two equal values next to each other in the highlighted list) is never allowed.
Highlighting a single day always works, and highlighting two days works when their values differ. Highlighted days need not be adjacent in nums.
Return the largest number of days that can be highlighted. The intended solution runs in O(n) time and O(1) extra space.
Example 1
- Input:
- nums = [4,9,2,7,3,8,1]
- Output:
- 7
- Explanation:
The values already go up, down, up, down, up, down, so all seven days can be highlighted.
Example 2
- Input:
- nums = [1,2,3,4,5]
- Output:
- 2
- Explanation:
The sequence only rises, so at most two days (for example 1 and 5) can be highlighted.
Example 3
- Input:
- nums = [3,8,8,2,2,6,1]
- Output:
- 5
- Explanation:
Skipping the repeated 8 and 2 leaves 3, 8, 2, 6, 1, which alternates up, down, up, down.
Constraints
- 1 ≤ nums.length ≤ 105
- -109 ≤ nums[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)