Number of Longest Increasing Subsequence

Problem

Given an integer array nums, let L be the length of its longest strictly increasing subsequence. Return how many distinct subsequences (by index set) of length L are strictly increasing. Two subsequences that pick different indices count separately even if they contain the same values.

• nums holds up to a couple thousand integers.
• Values can be negative or positive, well within a normal signed integer range.

Examples

• nums = [2, 4, 6, 5, 8] → 2. The longest length is 4, achieved by 2, 4, 6, 8 and 2, 4, 5, 8.
• nums = [7, 7, 7, 7, 7] → 5. Every increasing subsequence has length 1, and there are five single elements.
• nums = [2, 3, 5, 4, 6, 5, 8, 3] → 3. Length 5 via 2,3,5,6,8, 2,3,4,6,8, and 2,3,4,5,8.

Hints

1. Start from the O(n^2) LIS DP where length[i] is the longest increasing subsequence ending at i. What second quantity would you need per index to count them?
2. When extending i from an earlier j, there are three cases: j gives a strictly longer result, an equally long one, or a shorter one. What happens to the count in each?
3. Track count[i] alongside length[i]; on a strictly longer candidate reset the count to count[j], on a tie add count[j], then sum count[i] over indices with length[i] == max.