Standard Bar Dynamic Programming · DP on LIS O(n^2) · O(n)
Relay dispatch liked the longest-handoff analysis so much that ops now wants a census: not the length alone, but how many distinct chains achieve that record length. Two chains are different if they use a different set of station stops, even when their tag values coincide.
Input: An array nums of n integers.
Output: Return the number of longest strictly increasing subsequences of nums.
1 <= n <= 1000-10^4 <= nums[i] <= 10^4Input: {"nums":[1,3,5,4,7]}
Output: 2
1-3-5-7 and 1-3-4-7 both reach the record length 4.
Input: {"nums":[2,2,2,2,2]}
Output: 5
Strictness caps every chain at one element, and each of the five positions is such a chain.