673. Number of Longest Increasing Subsequence

Problem¶

Given nums, return how many index-distinct strictly increasing subsequences have the maximum possible length.

nums = [1, 3, 5, 4, 7]
longest subsequences = [1, 3, 5, 7], [1, 3, 4, 7]
output = 2

Key trick¶

For every index, track both:

The longest increasing subsequence length ending there.
The number of subsequences achieving that length.

When extending from an earlier smaller value, replace the count for a longer candidate or add the count for an equally long candidate.

Trap¶

Using <= instead of <, since the subsequence must be strictly increasing.
Counting distinct value sequences instead of index-distinct subsequences.
Overwriting counts when another predecessor produces the same optimal length.
Using the usual tails-only LIS algorithm, which discards information needed to count subsequences.

Why is it interesting?¶

It extends classic LIS dynamic programming by pairing every optimal length with the number of ways to achieve it.

Python solution¶

class Solution:
    def findNumberOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
        lengths = [1] * n
        counts = [1] * n

        for i in range(n):
            for j in range(i):
                if nums[j] >= nums[i]:
                    continue

                candidate = lengths[j] + 1

                if candidate > lengths[i]:
                    # A better length replaces both the previous length
                    # and all counts associated with it.
                    lengths[i] = candidate
                    counts[i] = counts[j]
                elif candidate == lengths[i]:
                    # Another predecessor achieves the same best length.
                    counts[i] += counts[j]

        best = max(lengths)
        return sum(count for length, count in zip(lengths, counts)
                   if length == best)

Time complexity: \(O(n^2)\).

Space complexity: \(O(n)\).

Comment on my solution¶

Your intuition that the tails algorithm loses necessary information and that sorting destroys the original order is correct. The missing local view is to treat each index as an endpoint and store both the best length and its count; combining these states makes this a direct dynamic programming problem.

# Ideas:
# - It reminds me of size of longest increasing subsequence
#   - whome solution uses an array of tails
# - This problem is in DP collection but it seems not DP
#   - I'll think a bit more
# - tails[i] , dp[i]
#   - updating tails misses information
#   - [1,3,5,4,2,7]
#     1
#     1 3
#     1 3 5
#     1 3 4
#     1 2 4
#     1 2 4 7
# - we need to capture the information
#   - the size longest increasing subsequence
#   - how many subsequence with that size
# - sorting doesn't seem an option???  we lose the order
# - what about knowing the max?  To do what?
# - if I know the number of subsequences of size 2, can I deduce the
#   number of subsequences of size 3???
# - the constraint seems global?  Is there a local way to look at it?

class Solution:
    def findNumberOfLIS(self, nums: list[int]) -> int: