# Number of Longest Increasing Subsequence LeetCode Solution

## Problem Description

The Number of Longest Increasing Subsequence LeetCode Solution problem involves finding the number of longest increasing subsequences in an array. Given an unsorted array of integers, the task is to find the length of the longest increasing subsequence and the number of such subsequences with that maximum length.

## Intuition

The problem can be approached using dynamic programming. We can maintain two arrays: `length` to store the length of the longest increasing subsequence ending at each index, and `count` to store the number of such subsequences. We iterate through the array, updating these arrays based on the increasing subsequence conditions.

## Solution Approach

1. Initialize two arrays: `length` of size `n` (length of the input array) and `count` of size `n`, both initialized to 1.
2. Iterate through the array with two nested loops. For each pair of indices (i, j) where `nums[i] < nums[j]`, update `length[j]` and `count[j]` based on the conditions.
3. Find the maximum length in the `length` array.
4. Iterate through the `length` array and accumulate the counts of subsequences with maximum length.
5. Return the maximum length and the count of such subsequences.

## Example Walkthrough

Consider the following array: `[1, 3, 5, 4, 7]`

1. Initialize `length` and `count` arrays: `[1, 1, 1, 1, 1]` and `[1, 1, 1, 1, 1]`.
2. Iterate through the array:
• For `nums[1] = 3`, update `length[1]` to 2 and `count[1]` to 1.
• For `nums[2] = 5`, update `length[2]` to 3 and `count[2]` to 1.
• For `nums[3] = 4`, update `length[3]` to 3 and `count[3]` to 1.
• For `nums[4] = 7`, update `length[4]` to 4 and `count[4]` to 2.
3. Find the maximum length, which is 4.
4. Accumulate counts of subsequences with length 4, which is 2.
5. Return the maximum length (4) and the count (2).

## Code Solutions

``````class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0

n = len(nums)
lengths = [1] * n
counts = [1] * n

for j in range(n):
for i in range(j):
if nums[i] < nums[j]:
if lengths[i] + 1 > lengths[j]:
lengths[j] = lengths[i] + 1
counts[j] = counts[i]
elif lengths[i] + 1 == lengths[j]:
counts[j] += counts[i]

max_length = max(lengths)
result = sum(count for length, count in zip(lengths, counts) if length == max_length)

return result
``````
``````class Solution {
public:
int findNumberOfLIS(vector& nums) {
if (nums.empty())
return 0;

int n = nums.size();
vector lengths(n, 1);
vector counts(n, 1);

for (int j = 0; j < n; j++) {
for (int i = 0; i < j; i++) {
if (nums[i] < nums[j]) {
if (lengths[i] + 1 > lengths[j]) {
lengths[j] = lengths[i] + 1;
counts[j] = counts[i];
} else if (lengths[i] + 1 == lengths[j]) {
counts[j] += counts[i];
}
}
}
}

int maxLength = *max_element(lengths.begin(), lengths.end());
int result = 0;

for (int k = 0; k < n; k++) {
if (lengths[k] == maxLength)
result += counts[k];
}

return result;
}
};
``````
``````class Solution {
public int findNumberOfLIS(int[] nums) {
if (nums == null || nums.length == 0)
return 0;

int n = nums.length;
int[] lengths = new int[n];
int[] counts = new int[n];

Arrays.fill(lengths, 1);
Arrays.fill(counts, 1);

for (int j = 0; j < n; j++) {
for (int i = 0; i < j; i++) {
if (nums[i] < nums[j]) {
if (lengths[i] + 1 > lengths[j]) {
lengths[j] = lengths[i] + 1;
counts[j] = counts[i];
} else if (lengths[i] + 1 == lengths[j]) {
counts[j] += counts[i];
}
}
}
}

int maxLength = Arrays.stream(lengths).max().orElse(0);
int result = 0;

for (int k = 0; k < n; k++) {
if (lengths[k] == maxLength)
result += counts[k];
}

return result;
}
}
``````

## Time and Space Complexity

Time Complexity: O(n^2) – Two nested loops are used to iterate through the array.

Space Complexity: O(n) – Additional arrays `lengths` and `counts` of size `n` are used.

## Sliding Window Algorithm in C and C++

Hello geeks 😁, In this article we are going to learn about the sliding window algorithm using C…

## For Loop in C Programming

Loops are an essential concept in programming that allow us to repeat a set of instructions multiple times.…

## Understanding the NXNXN Matrix Python 3: A Comprehensive Guide

NxNxN Matrix Python 3 are a powerful tool for handling complex data sets. These matrices, also known as…