Pattern - LIS Family

LIS problems share a structure: find the longest chain where each element can follow the previous based on some relation. Variants include: strictly increasing, non-decreasing, divisibility chains, 2D (two-dimensional) dominance (envelopes), string predecessor chains.

The $O(n^2)$ DP works for all: $dp[i] = 1 + \max(dp[j])$ for valid predecessors $j$. The $O(n \log n)$ binary search works when the relation is a total order. When you see "longest chain" or "maximum elements satisfying pairwise condition", think LIS.