Count Longest Rising Picks
Medium1-D Dynamic Programming
Problem
A rising pick from nums is a subsequence (original order, not necessarily adjacent) whose values are strictly increasing. Two picks are different if they use different sets of indices.
Return how many rising picks have the maximum possible length, modulo 10^9 + 7.
Example 1
- Input:
- nums = [1, 3, 5, 4, 7]
- Output:
- 2
The longest length is 4: [1, 3, 5, 7] and [1, 3, 4, 7].
Example 2
- Input:
- nums = [2, 2, 2, 2, 2]
- Output:
- 5
The longest length is 1, and each of the five positions is its own pick.
Constraints
- 1 ≤ nums.length ≤ 2000
- -10^6 ≤ nums[i] ≤ 10^6
Hint
Show the first hint
Start from the O(n²) longest-rising-subsequence table: len[i] = longest pick ending at i.
Walkthrough
How to approach it
01Clarify before coding
- Are equal values allowed in a pick? No, strictly increasing only.
- Do picks with the same values but different indices count separately? Yes, [1, 1, 2, 2, 3, 3] has 2·2·2 = 8 longest picks.
- Why modulo? Alternating pairs like [2, 1, 4, 3, ...] produce 2^(n/2) picks.
02Brute force
Enumerate every subset of indices, keep the strictly increasing ones, and count those of maximum length.
Cost: O(2^n · n): impossible beyond about 25 elements.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.