Problem Description

Question

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
-10⁶ <= nums[i] <= 10⁶
The answer is guaranteed to fit inside a 32-bit integer.

Solve it on LeetCode

Approaches

1. Dynamic Programming with Two Arrays

Intuition:

The problem is to find the number of longest increasing subsequences in the given array. Here, we will use a dynamic programming approach where one array will keep track of the length of the longest increasing subsequence ending at each index, and another array will keep the number of such subsequences.

Steps:

Create two arrays: lengths and counts.

lengths[i] will store the length of the longest increasing subsequence ending at index i.
counts[i] will store the number of longest increasing subsequences ending at index i.

Initialize each element of lengths to 1 because the minimum length of an increasing subsequence ending at any element is 1 (the element itself).
Initialize each element of counts to 1 because there's at least one subsequence ending at each element (the element itself).
Iterate through the array with two nested loops:

For each pair of indices (j < i), check if nums[j] < nums[i].
If it is, update the lengths and counts arrays.

If lengths[j] + 1 > lengths[i], it means we have found a longer subsequence by adding nums[i] to the subsequence ending at nums[j]. Thus, update lengths[i] and set counts[i] = counts[j].
If lengths[j] + 1 == lengths[i], it means we have found another subsequence of the same maximum length. Add counts[j] to counts[i].

After processing, find the maximum value in the lengths array, which represents the length of the longest increasing subsequence.
Sum up all values in counts where corresponding lengths are equal to the maximum value found in step 5.

Code:

Complexity Analysis

Time Complexity: O(n^2), where n is the length of the input array. This complexity arises due to the nested loops iterating over the array.
Space Complexity: O(n), as we are using two additional arrays lengths and counts to store information regarding the longest subsequences.

Number of Longest Increasing Subsequence

Ashish Pratap Singh