Last updated on October 5th, 2024 at 04:26 pm

Here, We see Number of Longest Increasing Subsequence LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Number of Longest Increasing Subsequence LeetCode Solution

Problem Statement

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.

1. Number of Longest Increasing Subsequence Leetcode Solution C++

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        const int n = nums.size();
        vector<int> lis(n,1);
        vector<int> count(n,1);
        int maxLen = 1;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    if(lis[j] + 1 > lis[i]){
                        lis[i] = lis[j] + 1;
                        count[i] = count[j];
                    }
					else if(lis[j]+1 == lis[i]){ 
                        count[i] += count[j];
                    }
                }
            }
            maxLen = max(maxLen,lis[i]);
        }
        int numOfLIS = 0;
        for(int i=0;i<n;i++){
            if(lis[i]==maxLen)
                numOfLIS += count[i];
        }
        return numOfLIS;
    }
};

2. Number of Longest Increasing Subsequence Leetcode Solution Java

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int[] dp = new int[n]; 
        int[] count = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);
        int maxLength = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == maxLength) {
                result += count[i];
            }
        }
        return result;
    }
}

3. Number of Longest Increasing Subsequence Leetcode Solution JavaScript

var findNumberOfLIS = function(nums) {
    let tracker = new Array(nums.length).fill(1);
    let frequency = new Array(nums.length).fill(1);
    for(let i = 0; i < nums.length; i++){
        for(let j = 0; j < i; j++){
            if(nums[j] < nums[i]){
                if(tracker[i] < tracker[j]+1){
                    tracker[i] = tracker[j]  + 1;
                    frequency[i] = frequency[j];
                } else if(tracker[i] === tracker[j]  + 1){
                    frequency[i] += frequency[j];
                }
            }
        }
    }
    const longestPath = Math.max(...tracker);
    let result = 0;
    for(let k = 0; k < nums.length; k++){
        if(tracker[k] === longestPath) result += frequency[k];
    }
    return result;
};

4. Number of Longest Increasing Subsequence Leetcode Solution Python

class Solution(object):
    def findNumberOfLIS(self, nums):
        n = len(nums)
        if n <= 1:
            return n
        lengths = [1] * n
        counts = [1] * n
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    if lengths[j] + 1 > lengths[i]:
                        lengths[i] = lengths[j] + 1
                        counts[i] = counts[j]
                    elif lengths[j] + 1 == lengths[i]:
                        counts[i] += counts[j]
        max_length = max(lengths)
        return sum(count for length, count in zip(lengths, counts) if length == max_length)