Start — the tallest staircase you can climb. Picture a row of stepping stones, each painted with a number. You may only hop forward, and every stone you land on must show a bigger number than the one before. What is the most stones you can step on? You're free to skip as many as you like — you just can never step down. That longest run of ever-increasing numbers is the Longest Increasing Subsequence. From $[3,\,1,\,4,\,1,\,5,\,9,\,2,\,6]$ one good climb is $1 \to 4 \to 5 \to 9$, four stones long.
Build — let each stone remember its own best climb. Give every stone a label $dp[i]$: the length of the best increasing run that ends on stone $i$. A lone stone is a run of one, so start every $dp[i]=1$. Now walk left to right. For stone $i$, look back at each earlier stone $j$ whose number is smaller ($A[j] < A[i]$); the best you can do is extend that stone's run by one, so $dp[i] = \max\big(dp[j]+1\big)$. The answer is the largest label anywhere, $\max_i dp[i]$. For $[3,\,1,\,4,\,1,\,5]$ the labels come out $1,\,1,\,2,\,1,\,3$, so the LIS length is $3$ — the run $1 \to 4 \to 5$.
Deepen — from $O(n^2)$ down to $O(n\log n)$. That look-back loop costs $O(n^2)$. A faster trick keeps one array $tails$, where $tails[k]$ holds the smallest possible ending value of any increasing run of length $k+1$. For each new number, binary-search the leftmost slot in $tails$ that is $\ge A[i]$ and overwrite it (or append if there is none). Because $tails$ always stays sorted, each step is $O(\log n)$, for $O(n\log n)$ overall — this is the "patience sorting" idea. One subtlety: $tails$ tells you only how long the LIS is, not which elements form it; reconstructing the actual run needs a separate predecessor array.
Try this in the sim above. The bars below animate a step-by-step ordering pass — a companion view of how sorting and increasing runs relate. Choose the Sorted preset: an already-sorted array is its own LIS, with length $n$. Choose Reverse: a strictly decreasing array has an LIS of just $1$, because no number is ever followed by a larger one. Then drag the n slider and watch the comparison count grow as the array gets longer.
§3 — Complexity Analysis & Derivation
Symbol
Meaning
n
Input size
T(n)
Time complexity
W(n)
Worst case
A(n)
Average case
Step 1 -- O(n^2) DP. dp[i] = length of LIS ending at index i. For each i: check all j < i where A[j] < A[i] and dp[j]+1 > dp[i]. Answer = max(dp). Two nested loops: O(n^2).
Step 2 -- O(n log n) Patience Sorting. Maintain array tails where tails[k] = smallest tail element of all increasing subsequences of length k+1. For each A[i]: find position pos (leftmost tails value >= A[i]) via binary search. Replace tails[pos] = A[i] or append. Length of tails = LIS length.
Step 3 -- Why Patience Sort Works. tails is always sorted (strictly increasing). Binary search finds correct pile. Replacing tails[pos] never increases LIS length but creates better opportunities for future extensions (smaller tail = easier to extend).
Step 4 -- Reconstructing the LIS. O(n^2) DP: track parent[i] = j that gave best dp[i]. Backtrack from max dp position. O(n log n): track additional predecessor array during patience sort. More complex but O(n log n) total.
Step 5 -- Strictly vs Non-strictly Increasing. Strictly increasing (A[j] < A[i]): use lower_bound in patience sort. Non-decreasing (A[j] <= A[i]): use upper_bound. Change the comparison in O(n^2) DP accordingly.
Step 6 -- Applications. Stock price analysis (longest upward trend). Version control (diff algorithms). Box stacking problem (reduce to LIS). Chain of pairs problem. RNA secondary structure prediction. Optimal BST construction.
§4 — Frequently Asked Questions
What does 'patience sorting' mean? concept+
Patience sort is a card game strategy: deal cards into piles where each card goes on the leftmost pile whose top card is >= the new card. The number of piles = LIS length. This is an analogy, not the actual card game. The algorithm uses binary search to find the correct pile efficiently.
Why does patience sort give the correct LIS length? complex+
Invariant: tails[k] = minimum possible tail value of any increasing subsequence of length k+1. This invariant is maintained by: (1) appending when A[i] > all tails (extends best LIS), (2) replacing tails[pos] with smaller A[i] (better opportunity for future). The length of tails at the end = LIS length.
Can LIS be reduced to LCS? concept+
Yes: sort A to get sorted_A, compute LCS(A, sorted_A). LCS gives LIS length in O(n^2). For the O(n log n) LIS, patience sort is better. The reduction shows LIS and LCS are related but LIS has a faster dedicated algorithm.
Where is LIS used in competitive programming? applied+
Box stacking (3D): sort by one dimension, find LIS by second. Sequence of pairs: sort by first element, LIS on second. Dilworth's theorem: minimum chains to cover a partial order = LIS length. RNA folding: maximize paired bases.
What is Dilworth's theorem connection? deep+
Dilworth's theorem: in any partially ordered set, the minimum number of chains needed to cover all elements equals the length of the longest antichain. By Mirsky's theorem: minimum number of antichains = LIS length. This connects LIS to combinatorics and scheduling theory.
How to find the actual LIS, not just its length? nonobv+
O(n^2): track parent[i]=j. Backtrack. O(n log n): track for each element which pile it went to and what the previous pile's top was. Store predecessor pointers. The reconstruction is O(n) after the O(n log n) preprocessing.
§5 — Misconceptions & Errors
Conceptual Misconceptions
✗ LIS can be solved greedily.
✓ Simple greedy (always extend the current sequence) fails. A[i] may start a new, eventually longer sequence. O(n^2) DP or O(n log n) patience sort is needed.
✗ Patience sort is O(n log n) because of sorting.
✓ Patience sort does NOT sort the input. It processes elements one by one and uses binary search on the tails array. No full sort needed.
✗ dp[i] = length of LIS up to index i (not ending AT i).
✓ dp[i] = LIS length ENDING at index i (including A[i]). The global LIS = max over all dp[i].
Implementation Errors
✗ Using tails.size() without binary search gives wrong replacement position.
✓ Must use lower_bound/upper_bound to find correct position. Simply pushing to the back only works if A[i] > all current tails (which is not always true).
✗ lower_bound and upper_bound give the same result for distinct elements.
✓ For strictly increasing LIS: use lower_bound (finds first >= A[i]). For non-decreasing: use upper_bound (finds first > A[i]). These differ for duplicates.
✗ The tails array stores the actual LIS.
✓ tails stores minimum tail values for each length -- NOT the actual LIS subsequence. To reconstruct the actual LIS, maintain a separate predecessor array.