Funcia
Lv.3binary-searchdpfenwick-tree

Number of Longest Increasing Subsequences

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

Given an integer array nums, let LL be the length of its longest strictly increasing subsequence (elements kept in their original order). Count the strictly increasing subsequences of length LL. Subsequences that pick different positions count as different even if their values are equal. Return the count modulo 1,000,000,0071{,}000{,}000{,}007.

Examples

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

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

Expected complexity

Time
O(N log N)
Space
O(N)

Examples

numsExpected
[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 O(log⁡N)O(\log N). Checking every pair j < i is O(N2)O(N^2) and exceeds the time limit.

Time limits per language

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

Test groups

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

No result yet. Run or submit your code.