Counting the best chains, not just their length
Track how many chains reach each position's best length, alongside the length itself. About 13 minutes.
How many longest chains are there?
Same rising chains, new question: how many different chains reach the longest length? In 1, 3, 5, 4, 7, both 1, 3, 5, 7 and 1, 3, 4, 7 have length 4, so the answer is 2.
Keep a second number next to each length: how many different chains end here with that best length. On its own, a number is 1 chain of length 1.
Beat the record, or tie it
Looking back at a smaller number, one of two things happens. If extending its chain beats the best length you had, that's a new record: throw away your old count and take over its count. If it only ties your best, it's simply more ways to get there: add its count to yours.
At the end, add up the counts of every position that reached the overall best length.
count = [1] * len(nums) # each starts with 1 way
2 and 1 each start their own chain: length 1, one way each.
Two earlier numbers each lead to a new best length of 4 here. One has 2 chains, the other has 1. How many chains of length 4 end here?
- A3
- B2
- C1
Show the answer
3. The first one sets the record with 2 chains; the second ties it and adds 1 more: 3.
Number of longest increasing subsequences
Given an array of integers nums, return how many distinct longest strictly increasing subsequences it has — subsequences that achieve the maximum possible length.
nums = [1, 3, 5, 4, 7] → 2
0 ≤ n ≤ 1,000 · −1,000,000,000 ≤ each value ≤ 1,000,000,000 · return a long