DP Dynamic programming Algorithm
Longest increasing subsequence
Also known as: LIS · patience sorting · Ulam's problem · longest non-decreasing subsequence
How many days of a five-year exchange rate series can be kept so that the rate only rises on them. The table of “each with each” answers in n², and a ladder of the lowest ends of chains in n log n: it is a card game of patience that was dealt in the 1960s to sort a deck. Vue’s list reordering and git’s patience diff run on it too.
From August 2021 to October 2026 the dollar cost between 414.67 and 549.15 tenge and moved almost every weekday, now up, now down. Let us throw out some days of this series so that on the remaining ones the rate only rises. How many days can be kept? 151 of 1900. There is no need to try sets of days for this: one pass over the series is enough, with a short “ladder” in hand: for each length of chain, the lowest rate such a chain can end on. The scene builds this ladder day by day; switch currencies, the rule and the order of days.
Each new day takes its rung. If it is above all the rungs, the ladder gets one rung longer. Otherwise it takes the place of the first rung that is not below it. As many rungs as there are at the end, so many days in the answer: 151 days, from 423.75 tenge on 4 August 2021 to 549.15 tenge on 2 October 2025, the most expensive day of the series. This took 11,838 comparisons. The table of “each day with each” would have made 1,804,050.
Days may be skipped, and that is the whole difference. In a row, without gaps, the dollar rose for at most six days: weekends cut off any rise. Switch the rule to “never down”: if neighbours in the chain may stand at the same rate, there are 269 days, almost twice as many. The reason is the calendar: the rate for Saturday, Sunday and Monday is almost always the same, and a non-strict chain picks up such triples whole. Press “Shuffle”: the same 1900 numbers in random order give a chain of only about 80 days. And on the “Years” tab is the mean temperature of Almaty over 85 years: the chain of ever warmer years stretches over 21 years, from 1954 to 2025, whereas shuffled years give 15 on average.
The idea
The longest increasing subsequence is the longest chain of elements taken in the same order as in the original sequence, but not necessarily consecutive, where each next one is greater than the previous. In the sequence 7, 2, 8, 1, 3, 4, 10, 6, 9, 5 such a chain is 1, 3, 4, 6, 9 or 2, 3, 4, 6, 9: length 5, and there may be several chains. A subsequence is not a run: the longest rising run can be found in one pass with a counter, while with gaps there are 2n options.
Of two chains of the same length, the one that ends lower is more useful: whatever extends the high one also extends the low one. So for each length k it is enough to remember one number, the lowest end of a chain of length k. These ends grow with k, forming a ladder. The next value x finds by binary search the first rung that is not below it and takes its place; if there is none, a new rung appears above the ladder. The ladder’s length at the end is the length of the answer, and the chain itself is recovered by pointers: each element remembers who stood on the rung below at the moment it arrived.
First, the table
The ladder looks like a trick, but it grew out of ordinary dynamic programming. What do you need to know about a chain to decide whether it can be extended? Only its last element. So the state is “a chain that ends at element i”, and L(i) is its greatest length:
$$L(i) = 1 + \max\{\, L(j) : j < i,\ a_j < a_i \,\},$$where the maximum of an empty set is zero: an element on its own is a chain of length 1. The answer is the largest L(i). The state “the best chain among the first i elements” will not do: it does not tell where the chain ended, and you cannot check whether ai can be appended to it. This is a common mistake on first meeting dynamic programming: the state must hold exactly what the continuation depends on.
The table is honest and short, but each cell looks at all the previous ones: n(n − 1)/2 comparisons. For 1900 days that is 1.8 million, for a million values half a trillion. To speed it up, notice that most of the table is not needed. Among all j with the same L(j) = k, only the one with the smallest aj matters for future elements: if a new element is greater than any of them, it is greater than the smallest. These smallest ones are the rungs of the ladder. The clearest explanation of how they behave was found long before programming contests, in the form of a card game of patience.
Patience
Cards are turned up one at a time and dealt into piles from left to right. A lower card may be put on a higher one, or it may start a new pile to the right of the others. The aim is to finish with as few piles as possible. Deal the deck yourself, then switch to “greedy”: each card goes on the leftmost pile it can be put on.
The ten cards 7, 2, 8, 1, 3, 4, 10, 6, 9, 5 are the example from the 1999 survey by David Aldous and Persi Diaconis. The greedy rule deals them into five piles: [7 2 1] [8 3] [4] [10 6 5] [9], from the bottom card to the top. Five piles, and the chain 1, 3, 4, 6, 9 of five cards. The coincidence is no accident.
However the deck is dealt, there are at least as many piles as cards in the longest increasing subsequence. The greedy rule gives exactly that many piles, and the pointers “the top card of the pile to the left at the moment the card was put down” give the subsequence itself.
At least. In each pile the cards only get higher from top to bottom: only a lower card is put on a card. An increasing chain goes in the order of dealing and each time takes a card higher than the previous one. Two of its cards cannot be in the same pile: the later would have been put on the earlier, which is higher. So all the cards of the chain are in different piles, and there are at least as many piles as cards in the chain.
Greedy gives exactly that many. In a greedy deal the top cards of the piles rise from left to right; this is checked by induction: a card goes on the leftmost pile whose top card is higher than it, and the order of the top cards is not broken. Let card c go into pile k > 1. It could not go into pile k − 1, so the top card of that pile is lower than c and comes earlier in the deck. A pointer leads from c to it. Follow the pointers from any card of the last pile: each step leads to a pile further left, to an earlier and lower card, and after as many steps as there are piles we reach the first. Read in reverse, the cards form an increasing chain of length “the number of piles”.
The two halves of the proof immediately give that the greedy rule beats any other and that its number of piles is the length of the longest increasing subsequence. And the top cards of the piles in a greedy deal are the ladder: they rise from left to right, so the leftmost suitable pile is found by binary search: the first top card that is not lower than the new one. In the listings this is bisect_left and sort.SearchInts. The card game turns into an O(n log n) algorithm.
The first half of the proof gives an old theorem of Paul Erdős and George Szekeres (1935): any sequence of n² + 1 distinct numbers has an increasing subsequence of length n + 1 or a decreasing one of the same length. Deal them greedily. If there are more than n piles, there is an increasing chain of n + 1 cards. If there are at most n piles, then one of them has at least n + 1 of the n² + 1 cards, and each pile, read from the bottom card to the top, is a decreasing subsequence.
Aldous and Diaconis suggest counting a game of patience with 52 cards as won if there are nine piles or fewer. In their 10,000 deals there were 11.6 piles on average, and a win in about 5% of cases. Try the full deck in the scene: the greedy deal cannot be beaten, but you can lose to it by putting cards down at random.
Code
Both versions side by side: the table by definition and patience with back pointers. The demo deals the ten cards from the example and checks the two ways against each other on two thousand random arrays.
The chains came out different, 1 3 4 6 9 for patience and 2 3 4 6 9 for the table, but the length is the same. Which of the equal chains the program gives out is decided by details: on ties the table keeps the first predecessor found, patience the card that lay on top of the pile to the left. Both are right.
Now the real series: three currencies against the tenge over five years and the mean temperatures of Almaty by year. The rates are stored in tiyn, as integers, so comparisons are exact. One function computes three different problems: a strictly rising chain, a non-decreasing one and a strictly falling one.
A trap: one word in a function name
bisect_left finds the first rung that is not less than x: an equal value takes the place of the equal one, and the ladder does not grow. This is strict increase. bisect_right finds the first rung greater than x, and an equal value sets a new rung above the equal one, giving a non-decreasing chain. On the dollar series that is 151 days and 269 days. Both problems are legitimate, but they must not be confused, and on data with repeats the difference is huge. For a decreasing chain, flip the sign of all the numbers and look for an increasing one; the listing does just that: for the dollar the strictly falling chain is 86 days against 151 days of rising.
The second trap is taking the ladder for the answer. After ten cards the rungs are 1, 3, 4, 5, 9, but there is no such chain in the deck: the five came last, after the nine. The ladder reports the length correctly, but the rungs themselves were set at different times and do not form a chain. Only the pointers recover the chain.
What it costs
Each element does one binary search over the ladder, which has at most L rungs, where L is the length of the answer: time O(n log L), in the worst case O(n log n). Memory is L numbers if only the length is needed, and O(n) pointers if the chain itself is. An algorithm that only compares elements cannot be substantially faster: in 1975 Michael Fredman showed that the ladder needs about n log n − n log log n comparisons and that in the worst case fewer will not do.
A measurement on random numbers: the table against the ladder.
The table’s slope is 2: a series twice as long, four times the work. The ladder’s slope is a little over one. With four thousand numbers the ladder in Python is a thousand times faster than the table, and it gets through a million numbers faster than the table gets through eight thousand.
There is a second way to speed up the table. L(i) is the maximum of L over all earlier elements with a value less than ai, that is, a prefix maximum query over values. If the values are compressed into numbers from 1 to n, such a query is answered by a Fenwick tree in O(log n). This is also O(n log n), but more flexible: the same way you can compute, for example, the greatest sum of an increasing subsequence, whereas the ladder does not work with weights: of two chains of the same length, a low end no longer means the better one.
The square root of n
How long is the chain of a series with no order at all? Stanisław Ulam asked this question in the early 1960s and, from Monte Carlo computations, conjectured that for a random permutation of n numbers the mean length grows as c√n. In 1972 John Hammersley proved that the limit c exists, and in 1977 Benjamin Logan and Lawrence Shepp and, at the same time, Anatoly Vershik and Sergei Kerov showed that c = 2. Over twenty years later Jinho Baik, Percy Deift and Kurt Johansson found how the length fluctuates around the mean: deviations of order n1/6 follow the Tracy–Widom distribution, the same one that describes the largest eigenvalue of a large random matrix.
Hence a correction to the mean too: it is closer to 2√n − 1.77·n1/6, and for 1900 numbers that is about 81. The listing shuffled the dollar rates a hundred times and got 80.8 on average, although our numbers are not all distinct, and repeats only shorten a strict chain. The real order of days gave 151, almost twice as many: the series has a direction.
A rough test for a trend can be built on this. For Almaty’s 85 years the chain of ever warmer years is 21 years. The same years, shuffled a thousand times, gave 15.3 on average, and a chain of 21 years or longer only three times. A new, warmer year comes too often for it to be an accident of order. The chain does not replace statistics: it does not say how fast it is warming, and one point thrown out can change it. The temperature here is the ERA5 reanalysis, a model estimate for the grid cell over the city, not the observations of a single station.
Where it works
Reordering page elements. When Vue 3 re-renders a keyed list, rows of a table, cards, menu items, the remaining elements have to be arranged in the new order. Each move is an insertBefore operation on a page element, and you want as few as possible. Vue writes out the old positions of the elements in the new order and finds their longest increasing subsequence: these elements already stand correctly relative to each other and are left alone, and only the others are moved. The function in Vue’s source is called getSequence, and it is the ladder with back pointers, the same as in the listings.
There cannot be fewer moves: the elements that were not touched kept their mutual order, so their old positions in the new order rise. So the fewest moves is n minus the length of the answer. This number is the Ulam distance between two permutations. As Ulam told Aldous and Diaconis, the idea came from thinking about the fastest way to sort the thirteen cards of a bridge hand. Reverse the list: one element stays in place, and all the others have to be moved.
A diff over unique lines. git diff --patience first finds the lines that occur exactly once in both the old and the new file: function headers rather than blank lines and braces. The pairs of such lines are ordered by the old file, and what is needed is the longest chain in which the positions in the new file rise too: the longest increasing subsequence. In git’s source (xdiff/xpatience.c) a comment describes the ladder in almost our words: for each length one sequence is kept, the one whose last element is smaller. The algorithm was devised by Bram Cohen and added to git by Johannes Schindelin in 2009; how such a diff differs from the usual one is in the article on Myers’ diff.
A common subsequence. If each character occurs once in each of two strings, their longest common subsequence is the longest increasing subsequence of positions: write out, for each character of the first string, its place in the second. When there are few matches, this trick works in the general case too; the 1977 algorithm of Hunt and Szymanski is built on it.
Chains by two features. Boxes that nest inside each other, tasks where both the deadline and the size matter: two-dimensional chains reduce to one-dimensional ones after the right sort. Exactly how is in the second problem below.
History
The game is older than the algorithm. According to Aldous and Diaconis, the name patience sorting was given to the game by Colin Mallows, and it was devised by A. S. C. Ross as a practical way to sort a deck: at the end of the deal the lowest card lies on top of the leftmost pile, the next one on top of some other, and the deck can be gathered in order by taking off top cards. Mallows analysed the game in 1960 and published the analysis much later. Robert Floyd discovered it independently in 1964 and discussed it in letters with Donald Knuth; this correspondence, according to the same authors, was never printed. That patience also finds the longest increasing subsequence was noticed independently by Hammersley.
The subsequences themselves appeared in mathematics even earlier, in the Erdős–Szekeres theorem of 1935. In 1961 Craige Schensted, to study longest increasing and decreasing subsequences, built a correspondence between permutations and pairs of Young tableaux: the length of the first row of the tableau equals the length of the longest increasing subsequence. Ulam’s question about random permutations eventually tied this combinatorics to random matrices. And programmers were left with a short ladder of binary search, which Vue runs every time the elements of a list swap places.
Problems
The first is the scene from the start of the article as a problem: the longest strictly rising chain of days and the days themselves, on real rates and on series of a hundred thousand days. In the second the chain is two-dimensional: boxes nest inside each other, and everything depends on how to sort boxes with an equal side.
A rate with no setbacks Nesting boxesData: Official tenge rates (the National Bank), the open data section of legost.in Almaty weather: the ERA5 reanalysis (Copernicus) via Open-Meteo, CC BY 4.0