the longest increasing subsequence
Given a sequence of numbers, a longest increasing subsequence is the longest selection of them — keeping their original left-to-right order but allowing gaps — whose values strictly increase. For the sequence 3, 1, 4, 1, 5, 9, 2, 6 one longest increasing subsequence is 1, 4, 5, 9 (or 1, 4, 5, 6) of length 4. It shows up when you want the longest run of improvement in time-ordered data, in patience-sorting card games, and as a clean exercise that has both a simple DP and a slicker one.
The simple DP defines dp[i] = the length of the longest increasing subsequence that ends exactly at index i. The clause 'ends at i' is the crucial state-design move: it fixes the last element so the future can be computed. The transition looks back at every earlier index j < i whose value is smaller, and extends the best such subsequence: dp[i] = 1 + max over j < i with a[j] < a[i] of dp[j], or just 1 if no smaller earlier element exists. The answer is the largest dp[i] over all i (the LIS need not end at the last element). With n elements and an O(n) scan per element this is O(n^2) time and O(n) space, and storing for each i the predecessor j that won lets you trace back the actual subsequence.
Two things are worth flagging. First, 'increasing' usually means strictly increasing; if equal values are allowed (non-decreasing), the comparison changes from a[j] < a[i] to a[j] <= a[i], so always confirm which the problem wants. Second, the O(n^2) version is the foundational one, but there is a well-known faster method that maintains, with binary search, the smallest possible tail value for an increasing subsequence of each length, achieving O(n log n) — that optimization belongs to the advanced toolkit, yet it is good to know the quadratic DP is not the last word. A subtle correctness point: dp[i] correctly counts the best ending at i because, by optimal substructure, an optimal increasing subsequence ending at i, with its last element removed, is an optimal increasing subsequence ending at the previous chosen index.
Sequence 3, 1, 4, 1, 5, 9, 2, 6. The dp array (longest increasing subsequence ending at each index) is 1, 1, 2, 1, 3, 4, 2, 4. The max is 4, achieved ending at the 9 or the final 6; tracing prev pointers from the 9 recovers 1, 4, 5, 9.
dp[i] looks back at all smaller earlier values and extends the best run ending before i.
Confirm whether 'increasing' means strictly increasing (use a[j] < a[i]) or non-decreasing (use a[j] <= a[i]); they give different answers. The O(n^2) DP here is foundational, but an O(n log n) binary-search method exists and is the practical choice for large n.