Pattern visualizer
Longest Increasing Subsequence
The key insight: any increasing subsequence ending at index i must have come from some earlier, smaller element — so the longest one ending at i is just 1 more than the best chain among all valid predecessors. dp[i] stores that length for the subsequence ending exactly at index i; filling it in means scanning every earlier index j and, whenever nums[j] is smaller, checking whether extending that chain beats what dp[i] already holds. Because every dp[j] for j < i is already known by the time you reach i, this one pass builds up the full table, and the answer is simply the largest value dp ever holds. Animated on: nums=[10,9,2,5,3,7,101,18], O(n^2) dp: dp[i] = length of LIS ending at index i.
Dynamic Programming
Initialize dp[i] = 1 for all i, each element alone is a subsequence of length 1
1FUNCTION lengthLIS(nums):2 n = the length of nums3 dp = a list of n ones (dp[i] = LIS length ending at i)4 FOR i from 1 to n-1:5 FOR j from 0 to i-1:6 IF nums[j] < nums[i]:7 dp[i] = the larger of dp[i] and dp[j] + 18 RETURN the largest value in dp
← / → step · space play · Home restart