Given integer array nums, return the number of longest increasing subsequences.
Input: [1,3,5,4,7] → Output: 2 (both [1,3,5,7] and [1,3,4,7])Input: [2,2,2,2,2] → Output: 5
Maintain two DP arrays: len[i] = LIS length ending at i, cnt[i] = count of such LIS. For each pair (i,j), update if we find better or equal LIS length.
- len[i] = 1, cnt[i] = 1 initially.
- For i from 1 to n-1: for j from 0 to i-1: if nums[j]
- If len[j]+1 > len[i]: len[i]=len[j]+1, cnt[i]=cnt[j].
- Elif len[j]+1 == len[i]: cnt[i]+=cnt[j].
- maxLen = max(len[]); return sum of cnt[i] where len[i]==maxLen.
class Solution {
public int findNumberOfLIS(int[] nums) {
int n = nums.length, maxLen = 0, result = 0;
int[] len = new int[n], cnt = new int[n];
java.util.Arrays.fill(len, 1); java.util.Arrays.fill(cnt, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
if (len[j] + 1 > len[i]) { len[i] = len[j]+1; cnt[i] = cnt[j]; }
else if (len[j] + 1 == len[i]) cnt[i] += cnt[j];
}
}
maxLen = Math.max(maxLen, len[i]);
}
for (int i = 0; i < n; i++) if (len[i] == maxLen) result += cnt[i];
return result;
}
}
- Time Complexity: O(N^2)
- Space Complexity: O(N)