Intuition What this page is forThe parent note LIS parent gave you two algorithms. But an algorithm you can only run on the "nice" example is half-learned. Here we hunt down every kind of input LIS can face — sorted, reverse-sorted, all-equal, empty, one element, ties in the middle, a real word problem, and an exam trap — and grind each one through both the O ( n 2 ) O ( n log n ) tails method until nothing can surprise you.
Before we start, one reminder of the two tools, in plain words:
Recall The two machines in one breathDP machine: dp[i] = length of the longest strictly-increasing chain that ends exactly at index i . Fill it left to right; the answer is the biggest value anywhere in dp.
Tails machine: tails[k] = the smallest value that can end a chain of length k+1. For each new x, find the leftmost tails[k] >= x and overwrite it; if none, append. Answer = len(tails).
Every array you can ever feed LIS falls into one of these cells . If you can do all of them, you have seen everything.
Cell
Input shape
What's tricky
Example ex.
C1
Already sorted (strictly increasing)LIS = whole array; every append, no replace
Ex 1
C2
Reverse sorted (strictly decreasing)LIS = 1; every element replaces tails[0]
Ex 2
C3
All equal strict LIS = 1; ties must NOT extend
Ex 3
C4
Degenerate size — empty / one elementlength 0 and 1; boundary of the loops
Ex 4
C5
Ties in the middle (mixed with real growth)>= vs > matters hereEx 5
C6
General zig-zag (the "normal" case)both machines must agree
Ex 6
C7
Negative numbers + a plateau signs don't matter, only order does
Ex 7
C8
Word problem (real-world)turning a story into an array
Ex 8
C9
Exam twist — non-decreasing LISswap lower_bound→upper_bound
Ex 9
C10
Reconstruct the actual sequence tails alone can't; need parentsEx 10
Now we cover each cell.
A = [1, 2, 3, 4, 5]
Forecast: guess the LIS length before reading on. Sorted increasing... how much of it is an increasing subsequence?
Step 1 — DP. Every earlier element is smaller than every later one, so dp[i] = dp[i-1] + 1.
dp = [1, 2, 3, 4, 5].
Why this step? For index i, the best predecessor j is always i-1 (largest dp[j]), and A [ j ] < A [ i ] j<i — so the chain just keeps growing.
Step 2 — Tails. Each x is bigger than everything in tails, so we append every time.
[1] → [1,2] → [1,2,3] → [1,2,3,4] → [1,2,3,4,5].
Why this step? There is never a tails[k] >= x, so the "replace" branch never fires. len(tails)=5.
Verify: the whole array is already strictly increasing, so the LIS is the array → length 5 . Both machines agree. ✓
A = [5, 4, 3, 2, 1]
Forecast: no two elements go "up" left-to-right. What can the longest increasing chain possibly be?
Step 1 — DP. No earlier element is smaller, so no dp[j]+1 ever wins. Every dp[i] = 1.
dp = [1, 1, 1, 1, 1].
Why this step? The condition A[j] < A[i] is false for every pair (5>4>3...), so the max over predecessors is empty → dp[i] = 1 + 0 = 1.
Step 2 — Tails. Every new x is smaller than the single tail, so it replaces tails[0] every time.
[5] → [4] → [3] → [2] → [1].
Why this step? lower_bound always finds tails[0] >= x, so we overwrite it. Length never grows past 1.
Verify: any single element is an increasing subsequence of length 1, and no longer one exists → 1 . Both agree. ✓ This is the worst case for LIS length, best case for "smallest tails" churn.
A = [7, 7, 7, 7] (strict LIS)
Forecast: equal is NOT "increasing". So what's the answer — 4 or 1?
Step 1 — DP. We need A[j] < A[i] strictly . But 7 < 7 dp = [1, 1, 1, 1].
Why this step? Strict LIS forbids equal neighbours; the recurrence's < filter throws them all out.
Step 2 — Tails with lower_bound (>=). For x=7: is there tails[k] >= 7? After the first append tails=[7], yes — tails[0]=7 >= 7, so we replace (overwrite 7 with 7, no growth).
[7] → [7] → [7] → [7].
Why lower_bound here? Using >= means an equal value lands on the same slot, never appending. That is exactly what stops ties faking a longer chain.
Verify: the longest strictly increasing chain among all-7's is one element → 1 . Both agree. ✓
(Contrast: if the problem wanted non-decreasing , the answer would be 4 — see C9.)
A = [] and A = [42]
Forecast: what should the length be with zero elements? With exactly one?
Step 1 — Empty array. The DP loop for i in 0..n-1 runs zero times, so dp is empty. max of an empty list is defined as 0 here (no subsequence exists).
Tails: never enters the loop → tails = [], len = 0.
Why this step? There are literally no indices i 1 < ⋯ < i L L
Step 2 — Single element. dp = [1]; answer 1. Tails: append 42 → [42], len = 1.
Why this step? One element alone is a valid (trivial) increasing subsequence.
Verify: empty → 0 , singleton → 1 . Both machines agree at the boundaries. ✓
Coding note: always guard max(dp) for the empty case, or it throws.
A = [1, 3, 3, 4] (strict LIS)
Forecast: two 3's sit in a row. Does the LIS use both, one, or neither?
Step 1 — DP.
i
A[i]
dp[i]
why
0
1
1
first
1
3
2
extend 1 (dp=1)
2
3
2
3 < 3 1 → dp=2
3
4
3
extend either 3 (dp=2) → 3
Why this step? The strict < blocks A[1]=3 from being a predecessor of A[2]=3, so both 3's have dp=2 independently.
Step 2 — Tails (lower_bound).
x=1 → [1].
x=3 → append → [1,3].
x=3 → leftmost tails[k] >= 3 is tails[1]=3, replace (3→3, no growth) → [1,3].
x=4 → append → [1,3,4]. len = 3.
Why this step? The second 3 lands on the same slot as the first — no fake length-3 chain like [1,3,3].
Verify: longest strictly increasing is [1,3,4] → 3 . Both agree. ✓
A = [3, 1, 4, 1, 5, 9, 2, 6]
Forecast: eyeball a long increasing chain, then count it.
Step 1 — DP.
i
A[i]
dp[i]
best predecessor
0
3
1
—
1
1
1
none smaller
2
4
2
idx 0 (3, dp 1) or idx 1 (1, dp 1)
3
1
1
none smaller
4
5
3
idx 2 (4, dp 2)
5
9
4
idx 4 (5, dp 3)
6
2
2
idx 1 or 3 (1, dp 1)
7
6
4
idx 4 (5, dp 3) — not idx 5, since A [ 5 ] = 9 > 6
answer = max(dp) = 4.
Why this step? We record the best chain ending at each i ; the global max picks the winner ([1,4,5,9] or [1,4,5,6]). Note at i=7 the predecessor must be smaller than 6, so 9 is disqualified and the chain hooks back to 5 at index 4.
Step 2 — Tails. 3→[3], 1→[1], 4→[1,4], 1→[1,4], 5→[1,4,5], 9→[1,4,5,9], 2→[1,2,5,9], 6→[1,2,5,6]. len = 4.
Why this step? The 2 quietly lowers tails[1] from 4 to 2 — bookkeeping, not a real subsequence — keeping options open. Length stays 4.
Verify: both give 4 . ✓
Read the figure below. Each blue box is an array element (its value inside, index i above, dp[i] below in yellow). A colored arrow runs from each element back to its chosen predecessor — the j that set dp[i]. Follow the green-ringed boxes [3,4,5,9]: that is one optimal length-4 chain, and you can see its arrows chain leftward 9→5→4→3. Notice how index 7 (6) has no arrow to index 5 (9) — the figure makes the "9 is too big to precede 6" fact visible.
A = [-2, -1, -1, 0, -3, 5] (strict LIS)
Forecast: negatives look scary, but LIS only cares about order , not sign. Guess the length.
Step 1 — DP.
i
A[i]
dp[i]
why
0
-2
1
first
1
-1
2
extend -2
2
-1
2
− 1 < − 1
3
0
3
extend either -1
4
-3
1
nothing smaller
5
5
4
extend 0 (dp 3)
Why this step? < treats -2 < -1 < 0 < 5 exactly like positives; the tie -1,-1 is blocked, the dip -3 restarts a chain.
Step 2 — Tails. -2→[-2], -1→[-2,-1], -1→[-2,-1] (replace), 0→[-2,-1,0], -3→[-3,-1,0] (replace tails[0]), 5→[-3,-1,0,5]. len = 4.
Why this step? -3 lowers the length-1 tail — harmless, keeps the chain length at 4.
Verify: longest strict chain is [-2,-1,0,5] → 4 . Both agree. Sign is irrelevant; only relative order counts. ✓
Worked example Ex 8 — Movie marathonYou have movies with running times (minutes) in the order they appear on a shelf:
T = [90, 120, 100, 150, 130, 200]. You want to pick movies left to right off the shelf so each is strictly longer than the last (building suspense). What's the most movies you can watch, in order?
Forecast: this is LIS in disguise — the "increasing" quantity is running time. Guess the count.
Step 1 — Model it. "Pick left to right, each strictly longer" = strictly increasing subsequence of T. So run LIS.
Why this step? "Keep original order + strictly bigger each time" is literally the LIS definition; no new algorithm needed.
Step 2 — Tails. 90→[90], 120→[90,120], 100→[90,100] (replace 120), 150→[90,100,150], 130→[90,100,130] (replace 150), 200→[90,100,130,200]. len = 4.
Why this step? Lowering the tails (120→100, 150→130) makes room for 200 to extend a longer chain: [90,100,130,200].
Verify (units): 4 movies, lengths in minutes 90 < 100 < 130 < 200 — strictly increasing ✓. Answer 4 movies .
Worked example Ex 9 — SameA = [1, 3, 3, 4], but now non-decreasing (equal is allowed)
Forecast: in C5 strict gave 3. With equals allowed, do the two 3's now both count?
Step 1 — Change the rule. Non-decreasing means A[j] <= A[i] in the DP filter, and in tails we switch to upper_boundtails[k] > x).
Why this step? Strict LIS uses >= so a tie overwrites the same slot; non-decreasing needs a tie to be allowed to append , which is exactly what > x (skip over equals) does.
Step 2 — DP run (non-decreasing).
i
A[i]
dp[i]
why
0
1
1
first
1
3
2
1 ≤ 3
2
3
3
now 3 ≤ 3 allowed → extend idx 1 (dp 2) → 3
3
4
4
3 ≤ 4
Why this step? The only change from C5 is < becoming <=; that single edit lets the second 3 stack on the first, lifting dp[2] from 2 to 3 and cascading to dp[3]=4.
Step 3 — Tails with upper_bound.
x=1 → [1].
x=3 → no tail >3 → append → [1,3].
x=3 → first tail >3? none (both 1,3 are <=3) → append → [1,3,3].
x=4 → append → [1,3,3,4]. len = 4.
Why this step? Now [1,3,3,4] is a legal non-decreasing chain of length 4.
Verify: non-decreasing longest = [1,3,3,4] → 4 (vs strict = 3). Both machines agree; the single >=↔> (and <↔<=) swap flips the answer. ✓
Worked example Ex 10 — Recover the sequence, not just its length, forA = [3, 1, 4, 1, 5, 9, 2, 6]
Forecast: the parent warned that tails alone can't give you the real chain. What extra do we store?
Step 1 — Use the DP table + parent pointers. From C6, dp = [1,1,2,1,3,4,2,4]. Store parent[i] = the j that gave dp[i] its value (or -1).
parent = [-1, -1, 0, -1, 2, 4, 1, 4].
Why this step? dp remembers how long , parent remembers from where — together they let us walk backwards.
Step 2 — Backtrack from the argmax. max(dp)=4 first occurs at index 5 (A[5]=9). Follow parents: 5 → 4 → 2 → 0, i.e. indices [0,2,4,5], values [3,4,5,9].
Why this step? Each parent hop peels off the last element of the optimal chain, reversing to reveal it.
Verify: 3 < 4 < 5 < 9, length 4 , matching C6's length. ✓ Note tails at the end was [1,2,5,6] — a different set of values (not even a real subsequence), proving you must keep parent, not read tails.
Recall Did we hit every cell of the matrix?C1 sorted (Ex 1) ✓ · C2 reverse (Ex 2) ✓ · C3 all-equal (Ex 3) ✓ · C4 empty/singleton (Ex 4) ✓ · C5 mid ties (Ex 5) ✓ · C6 zig-zag (Ex 6) ✓ · C7 negatives+plateau (Ex 7) ✓ · C8 word problem (Ex 8) ✓ · C9 non-decreasing twist (Ex 9) ✓ · C10 reconstruction (Ex 10) ✓. Every scenario the topic can throw is now worked.
Mnemonic One line to carry them all"Sorted grows, reversed stalls, ties freeze, empty is zero — < for strict, <= for slack, parent to rebuild."
Dynamic Programming — every C-cell was solved by the dp[i] ends-at-i state.Binary Search — lower_bound (C1–C8) vs upper_bound (C9) is the whole strict/non-decreasing switch.Patience Sorting — the tails traces above are literal card-pile runs.Greedy Algorithms — "keep smallest tail" justified every replace step.Russian Doll Envelopes — C10's reconstruction is the skill you reuse there.Longest Common Subsequence (LCS) — non-decreasing LIS (C9) equals LCS with sorted-with-duplicates.