Number of Longest Increasing Subsequence
Two DP arrays: len[i] = longest chain ending at i, cnt[i] = how many reach it
Length alone is not enough here — two different chains can both reach the same longest length, and both must be counted. So track a pair at every index: len[i] is the longest strictly increasing chain that ENDS at i, and cnt[i] is how many such longest chains end there. Scanning back over every smaller earlier value nums[j] < nums[i], one of two things happens: extending that chain beats anything found so far at i, which means a strictly longer chain was just discovered and the old count is thrown away in favor of cnt[j]; or it only TIES the best length already at i, which means another distinct way to reach that same length was found, so cnt[j] is added on top. Once every index is filled, the answer sums cnt[i] over every i where len[i] equals the overall maximum — not just the last such i, because several indices can independently terminate a longest chain.
Details
Animated on: nums = [1, 3, 5, 4, 7] — count how many DISTINCT strictly increasing subsequences share the maximum length.
Problem:Number of Longest Increasing SubsequenceMedium
Two DP arrays: len[i] = longest chain ending at i, cnt[i] = how many reach it
step 1 / 12
nums = [1, 3, 5, 4, 7]
Every element alone is an increasing subsequence of length 1, so len[i] = 1 and cnt[i] = 1 for every i to start.
1FUNCTION findNumberOfLIS(nums):2 n <- LENGTH(nums)3 len <- ARRAY of n ones4 cnt <- ARRAY of n ones5 FOR i FROM 1 TO n-1:6 FOR j FROM 0 TO i-1:7 IF nums[j] < nums[i]:8 IF len[j] + 1 > len[i]:9 len[i] <- len[j] + 110 cnt[i] <- cnt[j]11 ELSE IF len[j] + 1 = len[i]:12 cnt[i] <- cnt[i] + cnt[j]13 maxLen <- MAX(len)14 RETURN SUM of cnt[i] WHERE len[i] = maxLen
← / → step · space play · Home restart
Every step in words
Show all 12 steps
- Every element alone is an increasing subsequence of length 1, so len[i] = 1 and cnt[i] = 1 for every i to start.
- nums[0]=1 < nums[1]=3 and extending it beats anything found so far: len[1] <- len[0]+1 = 2. That's a strictly longer chain, so the old count is discarded and cnt[1] resets to cnt[0] = 1.
- nums[0]=1 < nums[2]=5 and extending it beats anything found so far: len[2] <- len[0]+1 = 2. That's a strictly longer chain, so the old count is discarded and cnt[2] resets to cnt[0] = 1.
- nums[1]=3 < nums[2]=5 and extending it beats anything found so far: len[2] <- len[1]+1 = 3. That's a strictly longer chain, so the old count is discarded and cnt[2] resets to cnt[1] = 1.
- nums[0]=1 < nums[3]=4 and extending it beats anything found so far: len[3] <- len[0]+1 = 2. That's a strictly longer chain, so the old count is discarded and cnt[3] resets to cnt[0] = 1.
- nums[1]=3 < nums[3]=4 and extending it beats anything found so far: len[3] <- len[1]+1 = 3. That's a strictly longer chain, so the old count is discarded and cnt[3] resets to cnt[1] = 1.
- nums[2]=5 is not < nums[3]=4, so j=2 cannot extend any subsequence ending at i=3; len[3] and cnt[3] are untouched by it.
- nums[0]=1 < nums[4]=7 and extending it beats anything found so far: len[4] <- len[0]+1 = 2. That's a strictly longer chain, so the old count is discarded and cnt[4] resets to cnt[0] = 1.
- nums[1]=3 < nums[4]=7 and extending it beats anything found so far: len[4] <- len[1]+1 = 3. That's a strictly longer chain, so the old count is discarded and cnt[4] resets to cnt[1] = 1.
- nums[2]=5 < nums[4]=7 and extending it beats anything found so far: len[4] <- len[2]+1 = 4. That's a strictly longer chain, so the old count is discarded and cnt[4] resets to cnt[2] = 1.
- nums[3]=4 < nums[4]=7 and extending it TIES the best length already at len[4]=4: this is another way to reach that same length, so cnt[4] += cnt[3] = 2.
- maxLen = 4, reached only at index 4, so the answer is just cnt[4] = 2.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.