Pattern visualizer
Number of Longest Increasing Subsequence
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. Animated on: nums = [1, 3, 5, 4, 7] — count how many DISTINCT strictly increasing subsequences share the maximum length..
Two DP arrays: len[i] = longest chain ending at i, cnt[i] = how many reach it
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