Algorithm
Problem Name: 673. Number of Longest Increasing Subsequence
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int findNumberOfLIS(int* nums, int numsSize) {
int i, j, k, res = 0, max_len = 0;
int *tmp, *len, *cnt;
if (numsSize == 0) return 0;
tmp = calloc(numsSize * 2, sizeof(int));
//assert(tmp);
len = &tmp[0];
cnt = &tmp[numsSize];
for (i = 0; i < numsSize; i ++) {
len[i] = cnt[i] = 1;
for (j = 0; j < i; j ++) {
if (nums[i] > nums[j]) {
if (len[i] < len[j] + 1) {
// reset the length and count
len[i] = len[j] + 1;
cnt[i] = cnt[j];
} else if (len[i] == len[j] + 1) {
// current summary
cnt[i] += cnt[j];
}
}
}
if (max_len < len[i]) {
max_len = len[i]; // reset
res = cnt[i];
} else if (max_len == len[i]) {
res += cnt[i]; // total
}
}
free(tmp);
return res;
}
Input
nums = [1,3,5,4,7]
Output
2
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int>len(n, 1);
vector<int>cnt(n, 1);
int maxlen = 1, res = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]){
if(len[i] == len[j] + 1) cnt[i] += cnt[j];
if(len[i] < len[j] + 1){
len[i] = len[j] + 1;
cnt[i] = cnt[j];
}
}
}
if(len[i] == maxlen> res += cnt[i];
if(len[i] > maxlen){
maxlen = len[i];
res = cnt[i];
}
}
return res;
}
};
Input
nums = [1,3,5,4,7]
Output
2
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int findNumberOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int[] count = new int[nums.length];
int maxVal = 0;
int res = 0;
for (int i = 0; i < nums.length; i ++) {
dp[i] = count[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
if (dp[i] == dp[j] + 1) {
count[i] += count[j];
}
else if (dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
count[i] = count[j];
}
}
}
if (dp[i] > maxVal) {
maxVal = dp[i];
res = count[i];
}
else if (dp[i] == maxVal) {
res += count[i];
}
}
return res;
}
}
Input
nums = [2,2,2,2,2]
Output
5
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const findNumberOfLIS = function(nums) {
if (nums.length === 0) return 0;
const len = new Array(nums.length);
const cnt = new Array(nums.length);
let max = 1;
let res=1;
len[0] = 1;
cnt[0] = 1;
for (let i = 1; i < nums.length; i++) {
len[i] = 1;
cnt[i] = 1;
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
if (len[j] + 1 > len[i]) {
cnt[i] = cnt[j];
len[i] = len[j] + 1;
} else if (len[j] + 1 === len[i]) {
cnt[i] += cnt[j];
}
}
}
if (len[i] > max) {
max = len[i];
res = cnt[i];
} else if (len[i] === max) {
res += cnt[i];
}
}
return res;
};
Input
nums = [2,2,2,2,2]
Output
5
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findNumberOfLIS(self, nums):
dp = [[1, 1] for _ in range(len(nums))]
for i in range(len(nums) - 1):
for j in range(i + 1, len(nums)):
if nums[j] > nums[i]:
if dp[i][0] >= dp[j][0]: dp[j] = [dp[i][0] + 1, dp[i][1]]
elif dp[i][0] == dp[j][0] - 1: dp[j][1] += dp[i][1]
dp.sort()
return dp and sum(d[1] for d in dp if d[0] == dp[-1][0]) or 0
Input
nums = [1,3,5,4,7]
Output
2