Problem Description

Given an integer array nums, your task is to find the number of longest strictly increasing subsequences in nums. A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements.

Constraints:

• Each element in nums can be used at most once in any subsequence.
• There may be multiple increasing subsequences of the same maximum length; you must count all such distinct subsequences.
• 1 ≤ nums.length ≤ 2000
• -106 ≤ nums[i] ≤ 106
• Output should be the total count of the longest increasing subsequences, not the subsequences themselves.

Thought Process

At first glance, this problem looks similar to the classic "Longest Increasing Subsequence" (LIS) problem, but with a twist: instead of just finding the length, we must count how many distinct LIS exist.

A brute-force approach would be to generate all possible subsequences, check which ones are increasing, and count those with the maximum length. However, this is extremely inefficient, since the number of subsequences grows exponentially with the input size.

To optimize, we can use dynamic programming. For each position in the array, we can keep track of:

• The length of the longest increasing subsequence ending at that position.
• The number of such subsequences ending at that position.

Solution Approach

We use dynamic programming with two arrays:

• lengths[i]: The length of the longest increasing subsequence ending at index i.
• counts[i]: The number of longest increasing subsequences ending at index i.

1. Initialize both arrays with 1s, because each element is an increasing subsequence of length 1 by itself.
2. For each index i, look at all previous indices j (where j < i):
   • If nums[j] < nums[i]:
     • If lengths[j] + 1 > lengths[i], we found a longer subsequence ending at i. Update lengths[i] and set counts[i] to counts[j].
     • If lengths[j] + 1 == lengths[i], it means another way to get the same LIS length at i. Add counts[j] to counts[i].
3. After processing all indices, the length of the LIS is max(lengths).
4. Sum up all counts[i] where lengths[i] equals the LIS length to get the total number of longest increasing subsequences.

Example Walkthrough

Let's walk through an example with nums = [1, 3, 5, 4, 7].

Step-by-step:

• Initialize: lengths = [1, 1, 1, 1, 1], counts = [1, 1, 1, 1, 1]
• At index 1 (nums[1]=3):
  • Compare with index 0 (1 < 3):
    • lengths[0]+1 = 2 > lengths[1] so update lengths[1]=2, counts[1]=1
• At index 2 (nums[2]=5):
  • Compare with 0 (1 < 5): lengths[0]+1=2 > 1 so lengths[2]=2, counts[2]=1
  • Compare with 1 (3 < 5): lengths[1]+1=3 > 2 so lengths[2]=3, counts[2]=1
• At index 3 (nums[3]=4):
  • Compare with 0 (1 < 4): lengths[0]+1=2 > 1 so lengths[3]=2, counts[3]=1
  • Compare with 1 (3 < 4): lengths[1]+1=3 > 2 so lengths[3]=3, counts[3]=1
  • Compare with 2 (5 < 4): no update
• At index 4 (nums[4]=7):
  • Compare with 0 (1 < 7): lengths[0]+1=2 > 1 so lengths[4]=2, counts[4]=1
  • Compare with 1 (3 < 7): lengths[1]+1=3 > 2 so lengths[4]=3, counts[4]=1
  • Compare with 2 (5 < 7): lengths[2]+1=4 > 3 so lengths[4]=4, counts[4]=1
  • Compare with 3 (4 < 7): lengths[3]+1=4 == 4 so counts[4]+=counts[3] (now counts[4]=2)

Time and Space Complexity

Brute-force approach:

• Time: O(2ⁿ), since all possible subsequences are checked.
• Space: O(n), for recursion stack.

• Time: O(n²), because for each index i we look at all previous indices j.
• Space: O(n), for the lengths and counts arrays.

Summary

The problem asks for the number of longest increasing subsequences in an array. By leveraging dynamic programming, we can efficiently track both the length and count of LIS ending at each position. This allows us to avoid redundant computation and solve the problem in O(n²) time. The key insight is to update counts in tandem with lengths, so all possible LIS are counted exactly once.

Code Implementation

class Solution:
    def findNumberOfLIS(self, nums):
        n = len(nums)
        if n == 0:
            return 0
        lengths = [1] * n  # lengths[i] = length of LIS ending at i
        counts = [1] * n   # counts[i] = number of LIS ending at i

        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    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]

        longest = max(lengths)
        return sum(c for l, c in zip(lengths, counts) if l == longest)
    

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> lengths(n, 1), counts(n, 1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    if (lengths[j] + 1 > lengths[i]) {
                        lengths[i] = lengths[j] + 1;
                        counts[i] = counts[j];
                    } else if (lengths[j] + 1 == lengths[i]) {
                        counts[i] += counts[j];
                    }
                }
            }
        }
        int longest = *max_element(lengths.begin(), lengths.end());
        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (lengths[i] == longest) res += counts[i];
        }
        return res;
    }
};
    

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int[] lengths = new int[n];
        int[] counts = new int[n];
        Arrays.fill(lengths, 1);
        Arrays.fill(counts, 1);

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    if (lengths[j] + 1 > lengths[i]) {
                        lengths[i] = lengths[j] + 1;
                        counts[i] = counts[j];
                    } else if (lengths[j] + 1 == lengths[i]) {
                        counts[i] += counts[j];
                    }
                }
            }
        }
        int longest = 0, res = 0;
        for (int len : lengths) longest = Math.max(longest, len);
        for (int i = 0; i < n; ++i) {
            if (lengths[i] == longest) res += counts[i];
        }
        return res;
    }
}
    

var findNumberOfLIS = function(nums) {
    const n = nums.length;
    if (n === 0) return 0;
    const lengths = new Array(n).fill(1);
    const counts = new Array(n).fill(1);

    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                if (lengths[j] + 1 > lengths[i]) {
                    lengths[i] = lengths[j] + 1;
                    counts[i] = counts[j];
                } else if (lengths[j] + 1 === lengths[i]) {
                    counts[i] += counts[j];
                }
            }
        }
    }
    const longest = Math.max(...lengths);
    let res = 0;
    for (let i = 0; i < n; ++i) {
        if (lengths[i] === longest) res += counts[i];
    }
    return res;
};