Number of Longest Increasing Subsequence

Problem Description

Given an integer array nums, return the number of longest increasing subsequences. Notice that the sequence has to be strictly increasing.

Key Insights

• The problem requires finding the length of the longest increasing subsequence (LIS) and counting how many such subsequences exist.
• Dynamic programming can be used to maintain two arrays: one for storing the lengths of the longest increasing subsequences up to each index, and another for counting the number of such subsequences.
• Each element can contribute to multiple increasing subsequences, so both the length and count must be updated accordingly.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

We will use a dynamic programming approach. We maintain two arrays:

1. dp: where dp[i] will store the length of the longest increasing subsequence that ends at index i.
2. count: where count[i] will store the number of longest increasing subsequences that end at index i.

The algorithm works as follows:

• Initialize the dp array with 1s since the minimum increasing subsequence length for each element is 1 (the element itself).
• Initialize the count array with 1s since there is at least one increasing subsequence of length 1 for each element.
• For each element in the array, check all previous elements to see if they can form an increasing subsequence.
• Update the dp and count arrays based on the comparisons, ensuring to correctly count the number of subsequences.

At the end, the maximum value in the dp array gives the length of the longest increasing subsequence, and the sum of counts corresponding to this maximum length provides the final count of such subsequences.

Code Solutions