812. Count the Longest Climbs
A hiker records the height of each checkpoint along a ridge in nums. A climb picks some checkpoints in the order they were visited, skipping the others, such that each picked height is strictly higher than the previous one.
Among all climbs, take the ones with the greatest number of picked checkpoints and count how many different such climbs exist. Two climbs are different when they use a different set of checkpoint positions, even if their heights are equal.
Return that count modulo 1000000007. Aim for time O(n^2) and extra space O(n).
Example 1
- Input:
- nums = [6,2,9,4,8,5,11]
- Output:
- 2
- Explanation:
The longest rising picks have 4 values and there are exactly two of them: 2, 4, 8, 11 and 2, 4, 5, 11.
Example 2
- Input:
- nums = [5,5,8,8,3]
- Output:
- 4
- Explanation:
Longest strict rises have 2 values: either 5 followed by either 8, so 2 x 2 = 4 ways.
Constraints
1 ≤ nums.length ≤ 1200
-106 ≤ nums[i] ≤ 106
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,000 msC++ 250 msJava 500 msJavaScript 500 msTypeScript 500 ms
Expected complexity
- Time
- O(n^2)
- Space
- O(n)