Visualize the Longest Increasing Subsequence algorithm step by step. Watch dp[i] values fill as the algorithm compares every pair, then backtrack to reveal the actual sequence.
Given an array of numbers, find the longest subsequence that is strictly increasing. Unlike sorting, elements must keep their original relative order. A cornerstone DP problem used in patience sorting, version history analysis, and RNA structure prediction.
A subsequence is a selection of elements that preserves original order but can skip elements. For [3, 10, 2, 1, 20], the LIS is [3, 10, 20] (length 3), not [3, 10, 2, 20], because 2 < 10 breaks the increasing order.
dp[i] = length of the longest increasing subsequence that ends at index i. Start with dp[i]=1 for all i (every single element is a subsequence of length 1). Then for each i, try every j < i where arr[j] < arr[i].
For each pair (j, i) where j < i: if arr[j] < arr[i], then we can extend the LIS ending at j with arr[i]. So dp[i] = max(dp[i], dp[j] + 1). The outer loop is O(n) and inner loop is O(n), giving O(n²) total.
The maximum value in dp[] is the LIS length. To reconstruct the actual sequence, we track a prev[] array: whenever dp[i] is updated via j, we set prev[i] = j. Backtrack from the index with dp = maxLen, following prev[] until -1.
The O(n²) DP approach is intuitive and handles all cases. An O(n log n) solution exists using patience sorting and binary search, but the DP version is the standard interview approach. The prev[] array is the key to reconstructing the actual subsequence.