DP problems — Longest Increasing Subsequence (LIS) — O(n²) and O(n log n): Question bank

Intuition The two mental pictures behind every question below

Keep these sketches in your head — the questions poke at them.

Picture 1 — "end-here DP" (the $O (n^{2})$ method). Draw the array as a row of dots. To fill dp[i], you look leftward at every earlier dot j that is lower than dot i, and stand on the tallest chain among them, then step up onto i. This is Dynamic Programming: solve a small ending-at-j problem, reuse it for the bigger ending-at-i problem.

Picture 2 — "card piles" (Patience Sorting, the $O (n lo g n)$ method). Deal cards left to right into piles. A card may only sit on a pile whose top is bigger than it, and you always drop it on the leftmost pile that accepts it; if none does, start a new pile on the right. tails[k] is just the top card of pile k. The number of piles = the LIS length. Choosing the leftmost pile is exactly what Binary Search does — and always keeping the top as small as possible is a greedy choice (see Greedy Algorithms): we never regret making a tail smaller, because a smaller top only lets more cards land later.

True or false — justify

TRUE or FALSE: The LIS must be a contiguous block of the array.

FALSE. LIS works on subsequences, so it may skip elements; e.g. in [10,9,2,5,3,7] the LIS [2,5,7] is non-contiguous.

TRUE or FALSE: For strict LIS, a value equal to a previous chosen value can extend the chain.

FALSE. "Strictly increasing" forbids equal neighbours, so [2,2,3] gives LIS length 2, not 3.

TRUE or FALSE: len(tails) at the end always equals the true LIS length.

TRUE. The length is provably correct even though the tails contents are not a real subsequence.

TRUE or FALSE: The final array tails is itself one valid longest increasing subsequence.

FALSE. tails is per-length bookkeeping whose entries were overwritten out of context; you need predecessor pointers to recover a real LIS.

TRUE or FALSE: The DP answer is always dp[n-1] (the last index).

FALSE. The LIS can end anywhere, so the answer is max over all dp[i]; dp[n-1] is only right if the optimum happens to end last.

TRUE or FALSE: tails is always kept strictly increasing during the algorithm.

TRUE. Chopping a longer chain yields a shorter chain with a smaller tail, and tails[k] is the smallest such tail, forcing tails to increase with length.

TRUE or FALSE: Replacing an entry in tails can ever change its length.

FALSE. A replacement overwrites an existing slot in place; only an append grows the length by one.

TRUE or FALSE: If the array is already strictly increasing, both methods return n.

TRUE. Every element extends the chain, so dp climbs 1,2,...,n and every x appends to tails.

TRUE or FALSE: If the array is strictly decreasing, the LIS length is 1.

TRUE. No element is bigger than an earlier one, so each stands alone; each x just replaces tails[0].

TRUE or FALSE: Reversing the array leaves the LIS length unchanged.

FALSE in general. Reversing

A

turns its LIS into the longest decreasing subsequence of the original, and those two lengths need not match — e.g. [1,2,4,3] has LIS length 3 but its reverse [3,4,2,1] has LIS length 2.

TRUE or FALSE: The

O (n lo g n)

method uses no dynamic programming ideas at all, only a greedy rule.

FALSE. Its "keep the smallest tail" rule is a greedy exchange argument (see Greedy Algorithms), but it still reuses per-length optimal sub-results like DP does; it merely replaces the DP inner loop with Binary Search.

Spot the error

Someone claims dp[i] means "LIS of the whole array up to index i". Why is that subtly wrong?

dp[i] must end exactly at i (use A[i] as its last element); "up to i" would be a prefix maximum, which is a different, weaker quantity.

Someone writes the recurrence as dp[i] = dp[i-1] + 1. What breaks?

That assumes the previous index is the predecessor; the predecessor is the best earlier j with A[j] < A[i], which may not be i-1 at all.

Someone uses upper_bound (first > x) for strict LIS. What goes wrong?

Equal values then append instead of replacing, creating a fake longer "increasing" chain like counting [2,2] as length 2.

Someone appends x to tails whenever x is not found by exact match. What's the bug?

You must append only when x exceeds all tails; otherwise you replace the first >= x. Appending on any "not exact" collapses the algorithm.

Someone returns max(tails) as the answer instead of len(tails). What's wrong?

The answer is the count of tails (number of achievable lengths), not the largest tail value; max(tails) is just an element of the array.

Someone initialises dp[i] = 0 instead of 1. What breaks?

Every element alone is an increasing subsequence of length 1, so the base must be 1; starting at 0 undercounts every answer by one.

Someone claims brute force is O(n^2) because there are n^2 pairs of indices (i,j). Why is that wrong?

True brute force lists every subsequence — one binary choice (keep/drop) per element — so it is O(2^n), not O(n^2); the n^2 pairs figure is the cost of the DP, which is a much cleverer method than brute force.

Someone recovers the LIS by reading tails left to right. What can go wrong?

The values in tails may come from non-adjacent, even out-of-order source positions, so they may not form a real subsequence of A; you need stored predecessor indices.

Why questions

Why do we force the subsequence to end at index i in the DP state?

It turns a global search into a local recurrence: any chain ending at i extends a chain ending at an earlier smaller j, so we only look backward.

Why is a smaller tail always at least as good in the

O (n lo g n)

method?

A smaller tail is easier to extend — more future elements exceed it — so greedily minimising each length's tail lets longer chains form more often.

Why can tails be binary-searched?

Because it is provably strictly increasing at all times, so lower_bound (first >= x) is well-defined and correct.

Why does the DP answer take a max over all dp[i] rather than a fixed index?

We do not know where the optimal LIS ends, so we compute the best ending at each position and take the overall maximum.

Why does replacing tails[k] with a smaller x never hurt correctness?

It only lowers the recorded tail for that length without changing the length; a smaller tail preserves every future extension and enables more, so no valid answer is lost.

Why does the "card piles" (patience) picture give the LIS length?

The number of piles equals len(tails); each pile's top is the smallest tail for that length, so the pile count is exactly the length of the longest increasing pick — see Patience Sorting.

Why is LIS related to LCS?

LIS(A) = LCS(A, sorted-unique(A)); a common subsequence with a sorted copy is exactly an increasing subsequence — see Longest Common Subsequence (LCS).

Why does Russian Doll Envelopes reduce to LIS?

After sorting by width (ties broken by descending height), the answer is the LIS on heights, so the 2D nesting problem becomes one 1D LIS.

Edge cases

What is the LIS of an empty array (n = 0)?

Length 0 — there are no elements, so no subsequence, and tails stays empty.

What is the LIS of a single-element array [7] (n = 1)?

Length 1 — the lone element is trivially an increasing subsequence; dp = [1], tails = [7].

What is the LIS of an all-equal array like [5,5,5,5] under strict increase?

Length 1 — no element strictly exceeds another; every x just replaces tails[0], leaving [5].

What is the LIS of [5,5,5,5] under non-decreasing rules?

Length 4 — with upper_bound (> x) the equal values append, giving the full length as expected.

How does the algorithm handle negative numbers or duplicates mixed in, e.g. [-1,-1,0]?

Fine — comparisons A[j] < A[i] and lower_bound work on any comparable values; strict LIS here is [-1,0], length 2.

For A=[0,1,0,3,2,3], what is the LIS length and why is the middle 0 harmless?

Length 4 ([0,1,2,3]); the second 0 replaces tails[0] (lowering the length-1 tail) but never shortens any existing chain.

Connections

Dynamic Programming — the "end-here" DP state pattern.
Binary Search — powers the lower_bound in the fast method.
Patience Sorting — the card-pile intuition for the pile count.
Greedy Algorithms — "keep smallest tail" is a greedy exchange argument.
Longest Common Subsequence (LCS) — LIS as LCS with a sorted copy.
Russian Doll Envelopes — 2D nesting reduced to 1D LIS.