Number of Longest Increasing Subsequence
Medium · Dynamic Programming · Array · Dynamic Programming · Binary Indexed Tree · Segment Tree
Problem
Given an integer array nums, return how many strictly increasing subsequences have the largest possible length.
Two subsequences are different when they use different sets of indices, even if their values are the same. The answer fits in a signed 32-bit integer.
Examples
Input: nums = [1,4,2,5,3] Output: 3
The longest length is 3, reached by 1, 4, 5 and 1, 2, 5 and 1, 2, 3.
Input: nums = [5,5,5,5] Output: 4
No two values increase, so the longest length is 1, and each of the four positions is one such subsequence.
Input: nums = [1,3,5,4,7] Output: 2
1, 3, 5, 7 and 1, 3, 4, 7 both have length 4.
Constraints
- 1 <= len(nums) <= 2000
- -10^6 <= nums[i] <= 10^6
- The answer fits in a signed 32-bit integer
Approaches
- Baseline: length and count per index, O(n²) — time O(n²), space O(n)
Follow-up
Without the guarantee that the answer fits 32 bits, the count can grow exponentially: [2, 1, 4, 3, 6, 5, …] has 2^(n/2) longest subsequences. Then return it modulo a prime, or use big integers.
Related problems
Start free on Cariara · Coding problems · System design studio
