Intuition The one core ideaLIS stands for Longest Increasing Subsequence . It asks: from a row of numbers, cross some out (never reorder the rest) so the survivors keep climbing — how long can that climbing line get? Everything else on this topic is just two ways of answering that one question quickly instead of trying all 2ⁿ cross-out patterns.
Before you can read the parent note fluently, you need a small toolbox of ideas. This page builds each one from zero , in the order they depend on each other. Nothing here is assumed — if the parent used a symbol, we define it here first.
Definition LIS — the acronym spelled outLIS = Longest Increasing Subsequence. "Longest" = we maximise the count; "Increasing" = the values must climb; "Subsequence" = we choose them by crossing others out without reordering. Keep all three words in mind — each one is a rule we make precise below.
Everything in this topic lives on top of one array — a row of boxes, each holding a number, each with an index (its position number) underneath.
A n array is an ordered row of values. We call it A length is how many boxes it has, written n n = 5
A [ 0 ] 0 , so the first box is index 0, not 1.)The little number under each box is its index .
Intuition Why start counting at 0?Almost every programming language does. Index 0 is the first element, and the last element is at index n − 1 n 0 , 1 , 2 , 3 , 4
Common mistake The empty array (n = 0 Why it's tempting to ignore: "who feeds in an empty array?" — but edge cases crash real code. The rule: if A no boxes (n = 0 no subsequence to climb, so LIS length is 0 . Both methods handle this for free: the O ( n 2 ) max d p tails array stays empty so its length is 0. Always state: empty array → answer 0 .
This is THE distinction the whole topic rests on.
Definition Subarray (contiguous)A subarray is a connected window — you pick a start box and an end box and take everything in between, no gaps. Like sliding a picture frame along the row.
Definition Subsequence (gaps allowed)A subsequence is what's left after you cross out some boxes and keep the rest in their original order . Gaps are allowed. You may cross out zero boxes, or all of them.
In the picture, [3, 4, 5] from [3,1,4,1,5] is a valid subsequence (we crossed out the two 1's) but not a subarray (the boxes aren't next to each other).
Common mistake "Reordering is allowed" — no.Why it's tempting: it feels like you're just picking a set of numbers. The fix: order is locked. You may only delete , never shuffle . [5, 3] is NOT a subsequence of [3,1,4,1,5] because 5 comes after 3 in the original.
Recall How many subsequences does a length-n 2 n n O ( 2 n )
Definition Strictly increasingA sequence is strictly increasing when each element is bigger than the one before it — never equal, never smaller. Symbol: the < sign between neighbours.
A [ i 1 ] < A [ i 2 ] < ⋯ < A [ i L ] up .
< symbol and what "strict" excludes
x < y x y Strict means we forbid x = y [2, 2, 3] is NOT strictly increasing (the two 2's are equal). If we allowed equals we'd say non-decreasing and write ≤ strict version.
< = strict = "must climb"≤ = loose = "may rest on a step"lower_bound vs upper_bound choice is entirely about which of these two you want.
The definition uses i 1 < i 2 < ⋯ < i L < signs are hiding here — don't confuse them!
i 1 < i 2 < ⋯ < i L i positions (box numbers), not values. i 1 < i 2 i 1 before position i 2 < enforces order preserved (no reordering).
Meanwhile A [ i 1 ] < A [ i 2 ] climbing .
So the full definition packs two rules:
Order: i 1 < i 2 < ⋯ < i L Climb: A [ i 1 ] < A [ i 2 ] < ⋯ < A [ i L ]
L L count of chosen elements — the length of the climbing line. LIS wants the biggest possible L
The parent's recurrence is
d p [ i ] = 1 + max ( { 0 } ∪ { d p [ j ] : j < i , A [ j ] < A [ i ]} ) .
max max ( S ) largest number in the collection S S max { 0 }
∪ { 0 } ∪ throw both collections together into one ". Here { 0 } even if no earlier element qualifies , the max d p [ i ] = 1
{ d p [ j ] : j < i , A [ j ] < A [ i ]} : as "such that ". This says: "collect d p [ j ] j such that j i and the value there is smaller." It's the set of all chains we could legally extend by tacking A [ i ]
Worked example Reading the whole recurrence in English"The best climbing line ending at box i i i
d p [ i ] dp is short for dynamic programming : solve small pieces, store their answers in a table, reuse them. d p [ i ] ends exactly at box i ." See Dynamic Programming for the general pattern. Pinning down where it ends is the trick that turns a global hunt into a simple left-to-right fill.
Definition Big-O notationO ( ⋅ ) how the work grows as the input gets big, ignoring constants. O ( n 2 ) n n n O ( n log n ) n
Intuition Why the recurrence isO ( n 2 ) d p [ i ] every earlier j < i to find valid predecessors (A [ j ] < A [ i ] n each of the n n n × n = n 2 O ( n 2 ) j O ( log n )
log n log 2 n how many times can I halve n " A list of 1024 needs only 10 halvings. This tiny number is why Binary Search
tails array
tails is the bookkeeping array behind the O ( n log n ) Patience Sorting ). ==tails[k] = the smallest possible last value of any increasing subsequence of length k + 1 always kept sorted (a longer chain's tail is bigger), so we can binary-search it. At the very end, len(tails) equals the LIS lengthtails stays empty, giving length 0. (Warning: tails is not itself a real subsequence; only its length is meaningful.)
On a sorted array, lower_bound(x) finds the position of the first element that is ≥ x (not less than x Binary Search — halving the range each step, hence O ( log n ) tails array for every element to decide whether to replace a tail or append a new one. upper_bound is its cousin: first element strictly greater (> x
Array A and index counting from 0
Subsequence delete keep order
Index chain i1 lt i2 order
max union set-builder notation
Dynamic Programming store subproblems
lower_bound and tails array
Feeds directly into the parent LIS note and connects onward to Patience Sorting and Greedy Algorithms .
What does the acronym LIS stand for? Longest Increasing Subsequence.
Given a length-5 array, what is the index of its last element? 4 (indices run 0 to n-1)
What is the LIS of an empty array (n = 0)? 0 — there is no subsequence to climb.
Is [5, 3] a subsequence of [3,1,4,1,5]? Why or why not? No — order is locked; you may delete but never reorder, and 5 comes after 3 in the original.
How many subsequences does a length-n array have? 2^n (each element kept or crossed out).
Is [2, 2, 3] strictly increasing? No — strict forbids equal neighbours; it is only non-decreasing.
In i 1 < i 2 Positions (indices) — this enforces original order, separate from the value comparison A [ i 1 ] < A [ i 2 ]
How do you get the overall LIS length from the dp table? Take the max over all cells: LIS = max over 0 ≤ i < n of dp[i], because the LIS can end at any index.
Why is the O(n²) recurrence quadratic? An inner loop scans all earlier j (up to n) for each of the n boxes → n × n = n² steps.
Why does the recurrence union in { 0 } So the max is defined even when no earlier smaller element exists, giving length 1 (element alone).
What does log 2 n How many times you can halve n before reaching 1.
What does tails[k] store in the fast method? The smallest possible last value of any increasing subsequence of length k+1 seen so far.
What does lower_bound(x) return on a sorted array? The position of the first element that is ≥ x
