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*

*List of all LeetCode Solution*

## Topics

Dynamic Programming

## Companies

## Level of Question

Medium

**Number of Longest Increasing Subsequence LeetCode Solution**

## Table of Contents

**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)