Longest Increasing Subsequence
The O(n^2) DP, the O(n log n) tails array with binary search, how to reconstruct the answer, and how LIS hides inside other problems.
The problem
Given an array, pick elements from left to right, keeping their order, so that each chosen element is larger than the previous one. The longest such pick is the longest increasing subsequence (LIS).
For [10, 9, 2, 5, 3, 7, 101, 18] the answer is 4, for example 2, 5, 7, 101. A subsequence may skip elements; a subarray may not.
1 of 9