Number of Longest Increasing Subsequences
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Given an integer array nums, let be the length of its longest strictly increasing subsequence (elements kept in
their original order). Count the strictly increasing subsequences of length . Subsequences that pick different
positions count as different even if their values are equal. Return the count modulo .
Examples
| nums | result |
|---|---|
[1, 3, 5, 4, 7] | 2 |
[2, 2, 2] | 3 |
[1, 2, 1, 2] | 3 |
Example 3 — The length-2 increasing subsequences use positions (0, 1), (0, 3) and (2, 3).
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 log N)
- Space
- O(N)
Examples
| nums | Expected |
|---|---|
[1,3,5,4,7] | 2 |
[2,2,2] | 3 |
[1,2,1,2] | 3 |
Hint
Hint
For each i keep len[i] (longest increasing subsequence ending at i) and cnt[i] (how many). Both come from the
predecessors with a strictly smaller value: take the maximum length and sum the counts of those achieving it. After
coordinate compression, a Fenwick tree of (length, count) pairs (combine: larger length wins, equal lengths add counts)
answers this in . Checking every pair j < i is and exceeds the time limit.
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 | 1084 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 | 11 | verdict only |
| performance | 60 | 4 | verdict only |