Number of Longest Increasing Subsequence
MediumArrayMath
Description
Given an integer array nums, return the number of longest increasing subsequences. There may be multiple subsequences with the maximum length.
Examples
Input:
nums = [1,3,5,4,7]Output:
2Explanation:
Two LIS of length 4: [1,3,4,7] and [1,3,5,7].
Input:
nums = [1]Output:
1Explanation:
Edge case with a single-element array.
Input:
nums = [2,2,2,2,2]Output:
5Explanation:
When all elements are equal, each individual element forms a longest increasing subsequence of length 1. Since there are 5 elements, there are 5 different LIS: [2], [2], [2], [2], [2] (each at different positions).
Constraints
- •
1 ≤ nums.length ≤ 2000
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.