A plugin registry dumps compatibility versions in the order they were declared — not sorted, not de-duplicated. Support wants the longest chain they can print as a supported upgrade path: each hop must go to a strictly higher version. Skipping entries is allowed. Adjacent-in-the-dump is not required.
versions = [10, 9, 2, 5, 3, 7, 101, 18]The intern who heard “increasing” scans for the longest contiguous run. That answers a different question: [3, 7, 101] has length 3. The real answer is length 4 — [2, 5, 7, 101] or [2, 3, 7, 18]. You may skip. You may not go backward. You may not pick a hole’s neighbor just because it sits next to a winner.
LIS is a subsequence: order preserved, holes allowed. Strictly increasing is the spec in this post. Enumerating every subset is O(2^n). The honest first table is O(n²): best length ending here. The title’s O(n log n) is patience — an array of tails plus a binary search — not a different problem.
This post is those two procedures. Families and the catalog live on the Algorithms Roadmap. The layout is already an array (Arrays). Contiguous maximum sum was Kadane; this job is length of an increasing pick, holes legal.
The O(n²) table: best ending here
At index i, any increasing subsequence that ends at i is a[i] alone, or some increasing subsequence that ended at an earlier j with a[j] < a[i], plus a[i]. You do not need every such j. You need the best length among them.
bestEndingHere[i] = 1 + max(bestEndingHere[j]) for j < i and a[j] < a[i] — or 1 if no such j. The answer is the max of that table.
static int lisLengthQuadratic(int[] a) {
int n = a.length;
if (n == 0) {
return 0;
}
int[] bestEndingHere = new int[n];
int best = 1;
for (int i = 0; i < n; i++) {
bestEndingHere[i] = 1;
for (int j = 0; j < i; j++) {
if (a[j] < a[i]) {
bestEndingHere[i] = Math.max(bestEndingHere[i], bestEndingHere[j] + 1);
}
}
best = Math.max(best, bestEndingHere[i]);
}
return best;
}Empty input is length 0. A singleton is 1. < is the spec: equal versions do not extend. Swap to <= and you have a different problem (non-decreasing) with a different table.
Note: This is the recurrence you should be able to write on a whiteboard. The n log n pass below does not replace the idea; it replaces the inner scan over every j.
A walk: four upgrades, not three
a = [10, 9, 2, 5, 3, 7, 101, 18]
i a[i] bestEndingHere[i] from
0 10 1 start
1 9 1 10 is not < 9
2 2 1 nothing smaller
3 5 2 2
4 3 2 2
5 7 3 5 or 3
6 101 4 7
7 18 4 7
best = 4At i = 6, 101 can sit after any earlier value. The best predecessor length is 3 (the 7), so 4. At i = 7, 18 cannot sit after 101, but it can sit after 7, so also 4. Two different subsequences share the max. The table stores lengths, not the picks.
Patience: tails plus binary search
You do not need every bestEndingHere[j]. You need, for each length k, the smallest tail value of any increasing subsequence of that length. Call that array tails. tails stays sorted. A smaller tail is a better hook for whatever comes next.
For each x in a:
- If
xis larger than every tail, it extends the longest subsequence seen — append. - Otherwise replace the first tail that is
>= x. That pile just got a smaller top.
That placement is a lower bound on a sorted prefix. Binary search already owns the loop and the miss encoding; here it is a subroutine, not a new lecture. The picture is patience sorting: leftmost pile whose top can take the card. The number of piles is the LIS length.
static int lisLength(int[] a) {
int n = a.length;
if (n == 0) {
return 0;
}
int[] tails = new int[n];
int size = 0;
for (int x : a) {
int i = Arrays.binarySearch(tails, 0, size, x);
if (i < 0) {
i = -(i + 1);
}
tails[i] = x;
if (i == size) {
size++;
}
}
return size;
}Search only the live prefix 0 .. size. The rest of the buffer is garbage. On a miss, Arrays.binarySearch returns -(insertionPoint) - 1; the insertion point is the first slot strictly greater than x. tails itself has no duplicates, so that slot is also the first >= x. A hit means x already sits on a pile — replace in place, length does not grow. That is the strictly-increasing contract.
Note: Non-decreasing (<=) needs the first tail strictly greater than x (upper bound), so equals can extend a pile. Do not flip one comparison in the quadratic table and keep this lower-bound replace. Pick a spec and implement both sides of it.
A tails walk — and why tails is not the sequence
Same dump:
x tails after the placement
10 [10]
9 [9]
2 [2]
5 [2, 5]
3 [2, 3]
7 [2, 3, 7]
101 [2, 3, 7, 101]
18 [2, 3, 7, 18]
size = 4[2, 3, 7, 18] happens to be a legal subsequence here. That is luck. tails[k] is the smallest ending of some subsequence of length k + 1. Those endings can come from different subsequences, so the tails row is not guaranteed to appear in order in a.
a = [3, 4, 2, 8, 1, 9]
3 → [3]
4 → [3, 4]
2 → [2, 4]
8 → [2, 4, 8]
1 → [1, 4, 8]
9 → [1, 4, 8, 9]
size = 4, but [1, 4, 8, 9] is not a subsequence:
1 is declared after 4 and 8. A real LIS is [3, 4, 8, 9].Do not return tails[0..size) and call it the upgrade path. Length is size. The path needs predecessor indices.
Recovering the path
Keep, beside each tail, the index in a that currently owns it. When you place a[i] at pos, if pos > 0 its predecessor is the index that owns pos - 1. Walk back from the owner of the longest tail.
static int[] lisSequence(int[] a) {
int n = a.length;
if (n == 0) {
return new int[0];
}
int[] tails = new int[n];
int[] tailsAt = new int[n];
int[] prev = new int[n];
Arrays.fill(prev, -1);
int size = 0;
for (int i = 0; i < n; i++) {
int pos = Arrays.binarySearch(tails, 0, size, a[i]);
if (pos < 0) {
pos = -(pos + 1);
}
tails[pos] = a[i];
tailsAt[pos] = i;
if (pos > 0) {
prev[i] = tailsAt[pos - 1];
}
if (pos == size) {
size++;
}
}
int[] seq = new int[size];
for (int idx = tailsAt[size - 1], k = size - 1; k >= 0; k--) {
seq[k] = a[idx];
idx = prev[idx];
}
return seq;
}On [3, 4, 2, 8, 1, 9] this walks 9 ← 8 ← 4 ← 3. Same length as tails. Actual hops.
Note: Ties keep the latest smallest tail. If the spec wants the lexicographically smallest path among several LIS, that is extra state — not this walk.
The slower cousin: LCS against a sorted unique copy
LIS of a is also the longest common subsequence of a and a sorted, de-duplicated copy of a. The shared order is “increasing.” That identity is correct. It is also the wrong default: you paid a sort plus an LCS grid for a one-sequence order question. The LCS post owns that grid. Do not rebuild it here to avoid writing tails.
Two sequences’ shared subsequence is LCS. One sequence’s increasing picks are LIS. Same family on the roadmap. Different job.
Complexity
| What | Cost | Why |
|---|---|---|
| Quadratic DP | O(n²) time, O(n) extra | Every j < i |
| Patience + binary search | O(n log n) time, O(n) extra | One lower bound per element |
| Reconstruct the path | O(n) extra | prev and tailsAt |
LCS vs sorted unique a | O(n²) via LCS, plus a sort | Correct, slower cousin |
| Every subset | O(2^n) | Not a strategy |
Length in O(n log n), linear extra memory; no JDK Arrays.lis. Tiny n can keep the quadratic table — the recurrence stays obvious. A staging dump of thousands of versions should not.
When not to use LIS
Skip this procedure when the job is not “longest strictly increasing subsequence.”
- You needed a contiguous run. Longest increasing subarray is one scan: extend while
a[i] > a[i - 1], else restart. Holes are illegal. LIS will skip and over-count that spec. - You needed non-decreasing. Duplicates must be allowed to extend. Change the quadratic
<to<=, and change the tails search to an upper bound. Do not mix the two. - You needed the path, not only the length.
lisLengthdoes not remember hops. Use predecessor indices. Do not printtails. - You needed a shared subsequence of two dumps. That is LCS, not “sort one side and hope.”
- You needed the count of LIS, or the lexicographically smallest among many. Extra DP state. Out of scope here.
nis a handful and you are explaining the recurrence. ShipbestEndingHere. The log factor is for the scan that no longer fits a nestedj.
Subsequence, strictly increasing, one sequence — that is the job. Contiguous, non-decreasing, or two-string overlap are different procedures that may look sorted.
Cheat sheet
Job: longest strictly increasing subsequence (holes OK)
Quadratic: bestEndingHere[i] = 1 + max bestEndingHere[j] for j<i, a[j]<a[i]
n log n: tails[k] = smallest tail of any IS of length k+1
Place x: lower bound on tails[0..size); replace or append
Length: size of tails — not the tails values
Path: prev[i] = owner of the previous length; walk back
Empty: length 0
Equals: do not extend (strict)
LCS cousin: LCS(a, sort(unique(a))) — correct, slower
JDK: Arrays.binarySearch on the live tails prefix; no Arrays.lis
Not this: increasing subarray, non-decreasing, two-string LCSDo:
- Name strictly increasing vs non-decreasing before the first comparison.
- Write
bestEndingHerefirst so the recurrence is obvious; then replace the innerjwith a lower bound. - Search
tailsonly on0 .. size. - Keep
previn the same pass if Support needs the hops, not only the count.
Don’t:
- Scan for a contiguous increasing run and call it LIS.
- Return
tailsas the subsequence. - Use LCS against a sorted copy as the production default.
- Flip
<to<=in one method and keep the other method’s bound.
Wrap-up
LIS replaces “every subset” with a per-index question: what is the best increasing subsequence that ends here? The O(n²) table makes that question literal. Patience keeps only the smallest tail of each length and places the next value with a binary search, so the length is O(n log n). The tails row is a set of hooks, not the path — walk predecessor indices when you need the upgrades. Empty is 0. Equals do not extend. Two dumps that must share a subsequence are LCS, not this pass.
The layout was already an array. The procedure is this table, then this bound. When the job is contiguous, non-decreasing, or two-string, start from the Algorithms Roadmap and pick again.