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(n2) DP works for all: dp[i]=1+max(dp[j]) for valid predecessors j. The O(nlogn) binary search works when the relation is a total order. When you see "longest chain" or "maximum elements satisfying pairwise condition", think LIS.