Algorithms / Lis Depth

Least You Need to Know: Longest Increasing Subsequence, Tails, and Reconstruction Intuition

LIS questions test whether you can separate the exact subsequence from the summary needed for its length. The two classic views are `dp[i]` for subsequences ending at `i` and the tails-array idea for faster length computation.

The least you need to know

`dp[i]` in the quadratic solution usually means the LIS length ending at index `i`.
The faster `tails` array stores best possible ending values for subsequences of each length, not an actual subsequence by itself.
Strictly increasing and nondecreasing versions use different binary-search conditions.
Reconstructing an actual LIS usually needs parent pointers or extra bookkeeping.
Sorting tricks such as Russian-doll envelopes often reduce to LIS after careful tie handling.

Key notation

dp[i] LIS length ending at position `i`

tails[len] smallest possible tail value of an increasing subsequence of that length

lower_bound first position with value at least the target

Tiny worked example

In the `O(n^2)` DP, compute `dp[i] = 1 + max(dp[j])` over earlier indices `j` with `a[j] < a[i]`.
In the faster method, maintain the smallest possible tail for each subsequence length and replace tails using binary search.

Common mistakes

The tails array supports LIS length efficiently, but it is not itself the final subsequence in general.
Strictness matters: the wrong binary-search variant changes the problem from increasing to nondecreasing.
A sorting reduction often needs one coordinate sorted descending on ties to avoid fake increases.

How to recognize this kind of problem

The prompt asks for a longest increasing pattern in a sequence or a 2D problem that can be reduced to one sorted dimension plus LIS.
You care about subsequence order, not contiguous subarrays.
The array is too large for brute-force subset search but small local comparisons still matter.