Given an integer array nums, return the number of longest increasing subsequences.
Notice that the sequence has to be strictly increasing.
Example 1:
Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].
Example 2:
Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.
Constraints:
1 <= nums.length <= 2000
-106 <= nums[i] <= 106
Intuition
Maintain a count array to keep count along with the dp array
Logic is, when you get the same 1 + dp[prev] == dp[index]
Means you got the sequence count again
So you incr the count of the count array
Links
Video Links
Approach 1:
Maintain dp & count array
C++
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
vector<int> ct(n,1);
int count = 1;
int maxi = 1;
for(int index=1; index<n; index++){
for(int prev=0; prev<index; prev++){
if(nums[prev] < nums[index] and 1+dp[prev] > dp[index]){
dp[index] = 1+dp[prev];
ct[index] = ct[prev];
}
else if(nums[prev] < nums[index] and 1+dp[prev] == dp[index])
ct[index] += ct[prev];
}
maxi = max( maxi, dp[index]);
}
int nos = 0;
// sum of all the count having seq as maxi
// LIS can be at different position
for(int i=0; i<n; i++){
if(dp[i]==maxi)
nos += ct[i];
}
return nos;
}
};