These are the notes for DSA episode 66. It's class photo day: eight students stand in roll-number order with heights 150, 142, 135, 140, 138, 145, 160, 155 cm. The PT teacher wants heights rising from left to right, but nobody may swap places; a student can only step out. How many can stay? The answer, 4 (for example 135, 140, 145, 160), is the longest increasing subsequence (LIS). We write the obvious keep-or-skip recursion (Time Limit Exceeded on 60 students), fix it with the DP dp[i] = longest line ending at i (which then times out on 200,000 numbers), and finally invent the tails array with binary search: O(n log n), a million numbers in milliseconds. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).
The problem, in real life
| Class photo day | In code |
|---|---|
| Students in roll-number order | the array nums, order fixed |
| A student's height | nums[i] |
| Step out of the line | delete an element |
| Heights rising left to right | strictly increasing |
| Students who stay | a subsequence |
| Most students who can stay | the length of the LIS |
| Fewest students sent out | n - LIS |
Every word, from zero
- Subsequence: what is left after deleting some elements (maybe none, maybe all) while the rest keep their order.
[135, 140, 145, 160]is a subsequence of the heights. - Subarray: a contiguous block. Every subarray is a subsequence, but not the other way round.
- Strictly increasing: every element is bigger than the one before (
<, not≤). Non-decreasing allows equal neighbours. - LIS: the longest strictly increasing subsequence. We usually want its length; sometimes the elements too.
- Brute force: trying every possibility.
nelements have2^nsubsequences. - State: the few numbers that describe a sub-problem. For the recursion:
(i, last kept value); for the DP:ialone. - dp[i]: the length of the longest increasing subsequence that ends exactly at index i.
- tails[k]: the smallest possible last value of any increasing subsequence of length
k + 1seen so far. - Binary search: halving a sorted range to find a position in
O(log n)steps (episode 12). - Lower bound: the first position whose value is
≥ x. Upper bound: the first position whose value is> x. - Insertion point: where
xwould go to keep an array sorted;Arrays.binarySearchreturns-(insertion point) - 1whenxis missing. - Patience sorting: the card game this algorithm comes from: deal each card onto the leftmost pile whose top card is
≥it; the number of piles is the LIS.
Problem statement
Given an integer array nums, return the length of the longest strictly increasing subsequence (LeetCode 300).
| nums | Answer | One LIS |
|---|---|---|
[150, 142, 135, 140, 138, 145, 160, 155] |
4 |
135, 140, 145, 160 |
[0, 1, 0, 3, 2, 3] |
4 |
0, 1, 2, 3 |
[] |
0 |
(empty) |
[7, 7, 7, 7] |
1 |
7 (equal is not increasing) |
[5, 4, 3, 2, 1] |
1 |
any single number |
Constraints in the video: n ≤ 200,000. LeetCode 300 has n ≤ 2500 and asks for O(n log n) as the follow-up.
Obvious correct idea: keep or skip every student
Walk left to right and remember the last height kept. Each student is either skipped, or kept if taller than the last one kept. At the start nothing is kept, so last = Integer.MIN_VALUE.
import java.util.*;
public class Main {
static int lis(int[] nums) {
return best(nums, 0, Integer.MIN_VALUE);
}
static int best(int[] nums, int i, int last) {
if (i == nums.length) return 0;
int skip = best(nums, i + 1, last);
if (nums[i] <= last) return skip;
int take = 1 + best(nums, i + 1, nums[i]);
return Math.max(skip, take);
}
public static void main(String[] args) {
System.out.println(lis(new int[]{150, 142, 135, 140, 138, 145, 160, 155}));
System.out.println(lis(new int[]{0, 1, 0, 3, 2, 3}));
System.out.println(lis(new int[]{}));
System.out.println(lis(new int[]{7, 7, 7, 7}));
System.out.println(lis(new int[]{5, 4, 3, 2, 1}));
}
}
Output:
4
4
0
1
1
Correct, but now 60 students, heights mostly rising with small dips (h[i] = 120 + i + (i % 4) * 2):
import java.util.*;
public class Main {
static int lis(int[] nums) {
return best(nums, 0, Integer.MIN_VALUE);
}
static int best(int[] nums, int i, int last) {
if (i == nums.length) return 0;
int skip = best(nums, i + 1, last);
if (nums[i] <= last) return skip;
int take = 1 + best(nums, i + 1, nums[i]);
return Math.max(skip, take);
}
public static void main(String[] args) {
int n = 60;
int[] h = new int[n];
for (int i = 0; i < n; i++) h[i] = 120 + i + (i % 4) * 2;
long t0 = System.nanoTime();
int best = lis(h);
System.out.println("60 students: " + best + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
}
}
Output: nothing for 25 seconds, then Time Limit Exceeded. (On this machine 30 students took 39 ms, 34 took 373 ms, 36 took 597 ms: every few students multiply the time.)
Why is it slow?
Every student doubles the choices (keep or skip): up to 2^60 subsequences. But a call only depends on (i, last kept value), and last is always one of the earlier students, so there are only about n² different questions; the recursion answers the same ones again and again. Flip the question: instead of "what comes next?", ask "what is the longest rising line that ends at student i?"
The O(n²) DP: dp[i] = longest line ending at i
- State:
dp[i]= length of the longest increasing subsequence that ends exactly ati. - Alone:
dp[i] = 1. - Extend: for every
j < iwithnums[j] < nums[i],dp[i] = max(dp[i], dp[j] + 1). - Answer:
max(dp[i])over alli(the line can end anywhere).
By hand
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| height | 150 | 142 | 135 | 140 | 138 | 145 | 160 | 155 |
| dp[i] | 1 | 1 | 1 | 2 | 2 | 3 | 4 | 4 |
150, 142, 135: nobody shorter before them, 1. 140 and 138 follow 135: 2. 145 follows 140 or 138: 3. 160 and 155 follow 145: 4. Answer max = 4.
import java.util.*;
public class Main {
static int lis(int[] nums) {
int n = nums.length, best = 0;
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++)
if (nums[j] < nums[i])
dp[i] = Math.max(dp[i], dp[j] + 1);
best = Math.max(best, dp[i]);
}
return best;
}
public static void main(String[] args) {
System.out.println(lis(new int[]{150, 142, 135, 140, 138, 145, 160, 155}));
System.out.println(lis(new int[]{0, 1, 0, 3, 2, 3}));
System.out.println(lis(new int[]{}));
System.out.println(lis(new int[]{7, 7, 7, 7}));
System.out.println(lis(new int[]{5, 4, 3, 2, 1}));
int n = 60;
int[] h = new int[n];
for (int i = 0; i < n; i++) h[i] = 120 + i + (i % 4) * 2;
long t0 = System.nanoTime();
int best = lis(h);
System.out.println("60 students: " + best + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
}
}
Output:
4
4
0
1
1
60 students: 32, 0 ms
The 60 students are instant now. But with 200,000 random numbers (new Random(42)), the double loop does 200,000² / 2 = 20 billion comparisons: Time Limit Exceeded (on this machine: 50,000 numbers took 4.2 s, 100,000 took 16.9 s; 200,000 would take about a minute).
The key insight: the tails array
- Whether a new student can join a line at the end depends only on the line's last height.
- Of two lines with the same length, the one with the lower end is always at least as good (anything that extends the other also extends it).
- So keep one number per length:
tails[k]= the smallest last value of any increasing subsequence of lengthk + 1. tailsis always sorted: a line of lengthk + 2contains a line of lengthk + 1that ends lower.- For each new
x: binary search the first tail≥ x(lower bound). Replace it withx(same length, lower end); if there is none, appendx(a longer line). The answer is the length oftails.
By hand
| x | first tail ≥ x | tails after |
|---|---|---|
| 150 | none: append | [150] |
| 142 | 150 | [142] |
| 135 | 142 | [135] |
| 140 | none: append | [135, 140] |
| 138 | 140 | [135, 138] |
| 145 | none: append | [135, 138, 145] |
| 160 | none: append | [135, 138, 145, 160] |
| 155 | 160 | [135, 138, 145, 155] |
Length 4. Each student cost one binary search.
Solution in Java: tails + binary search
import java.util.*;
public class Main {
static int lis(int[] nums) {
int[] tails = new int[nums.length];
int len = 0;
for (int x : nums) {
int lo = 0, hi = len;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (tails[mid] < x) lo = mid + 1;
else hi = mid;
}
tails[lo] = x;
if (lo == len) len++;
}
return len;
}
public static void main(String[] args) {
System.out.println(lis(new int[]{150, 142, 135, 140, 138, 145, 160, 155}));
System.out.println(lis(new int[]{0, 1, 0, 3, 2, 3}));
System.out.println(lis(new int[]{}));
System.out.println(lis(new int[]{7, 7, 7, 7}));
System.out.println(lis(new int[]{5, 4, 3, 2, 1}));
}
}
Output:
4
4
0
1
1
The empty array never enters the loop (0); equal numbers find themselves with the lower bound and replace instead of appending (1 for [7, 7, 7, 7]); a decreasing array keeps replacing tails[0] (1).
The big inputs (60 students, then 200,000 and 1,000,000 random numbers):
import java.util.*;
public class Main {
static int lis(int[] nums) {
int[] tails = new int[nums.length];
int len = 0;
for (int x : nums) {
int lo = 0, hi = len;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (tails[mid] < x) lo = mid + 1;
else hi = mid;
}
tails[lo] = x;
if (lo == len) len++;
}
return len;
}
public static void main(String[] args) {
int n = 60;
int[] h = new int[n];
for (int i = 0; i < n; i++) h[i] = 120 + i + (i % 4) * 2;
long t0 = System.nanoTime();
int best = lis(h);
System.out.println("60 students: " + best + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
for (int m : new int[]{200000, 1000000}) {
int[] a = new int[m];
Random rnd = new Random(42);
for (int i = 0; i < m; i++) a[i] = rnd.nextInt(1000000000);
long t1 = System.nanoTime();
int b = lis(a);
System.out.println(m + " numbers: " + b + ", " + (System.nanoTime() - t1) / 1000000 + " ms");
}
}
}
Output:
60 students: 32, 0 ms
200000 numbers: 881, 15 ms
1000000 numbers: 1995, 58 ms
Which students stay? tailIdx + prev
tails gives the length, not the line: it can mix different lines. Store indexes instead (tailIdx[k] = the student ending the best line of length k + 1), and when student i lands at position k, remember prev[i] = tailIdx[k - 1], the student before it. At the end, walk prev back from tailIdx[len - 1].
import java.util.*;
public class Main {
static List<Integer> line(int[] h) {
int n = h.length, len = 0;
int[] tailIdx = new int[n], prev = new int[n];
for (int i = 0; i < n; i++) {
int lo = 0, hi = len;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (h[tailIdx[mid]] < h[i]) lo = mid + 1;
else hi = mid;
}
prev[i] = lo > 0 ? tailIdx[lo - 1] : -1;
tailIdx[lo] = i;
if (lo == len) len++;
}
LinkedList<Integer> out = new LinkedList<>();
for (int i = len > 0 ? tailIdx[len - 1] : -1; i != -1; i = prev[i])
out.addFirst(h[i]);
return out;
}
public static void main(String[] args) {
System.out.println(line(new int[]{150, 142, 135, 140, 138, 145, 160, 155}));
System.out.println(line(new int[]{0, 1, 0, 3, 2, 3}));
System.out.println(line(new int[]{140, 145, 150, 135}));
System.out.println(line(new int[]{}));
}
}
Output:
[135, 138, 145, 155]
[0, 1, 2, 3]
[140, 145, 150]
[]
The same solution in C++
std::lower_bound is exactly "the first tail ≥ x".
#include <bits/stdc++.h>
using namespace std;
// Longest increasing subsequence: tails + binary search, O(n log n).
int lis(const vector<int>& nums) {
vector<int> tails;
for (int x : nums) {
auto it = lower_bound(tails.begin(), tails.end(), x); // first tail >= x
if (it == tails.end()) tails.push_back(x);
else *it = x;
}
return tails.size();
}
// The actual subsequence: tailIdx + prev, then walk back.
vector<int> line(const vector<int>& h) {
int n = h.size();
vector<int> tailIdx, prev(n, -1);
for (int i = 0; i < n; i++) {
int lo = 0, hi = tailIdx.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (h[tailIdx[mid]] < h[i]) lo = mid + 1;
else hi = mid;
}
if (lo > 0) prev[i] = tailIdx[lo - 1];
if (lo == (int)tailIdx.size()) tailIdx.push_back(i);
else tailIdx[lo] = i;
}
vector<int> out;
for (int i = tailIdx.empty() ? -1 : tailIdx.back(); i != -1; i = prev[i]) out.push_back(h[i]);
reverse(out.begin(), out.end());
return out;
}
int main() {
cout << lis({150, 142, 135, 140, 138, 145, 160, 155}) << "\n";
cout << lis({0, 1, 0, 3, 2, 3}) << "\n";
cout << lis({}) << " " << lis({7, 7, 7, 7}) << " " << lis({5, 4, 3, 2, 1}) << "\n";
for (int v : line({150, 142, 135, 140, 138, 145, 160, 155})) cout << v << " ";
cout << "\n";
mt19937 rng(42);
vector<int> a(1000000);
for (int& x : a) x = rng() % 1000000000;
cout << "1000000 numbers: " << lis(a) << "\n";
}
Output (g++ 13, -O2):
4
4
0 1 1
135 138 145 155
1000000 numbers: 1987
(The C++ and Python random generators differ from Java's, so the million-number answers differ.)
The same solution in Python
bisect.bisect_left is the lower bound.
from bisect import bisect_left
import random
# Longest increasing subsequence: tails + binary search, O(n log n).
def lis(nums):
tails = []
for x in nums:
k = bisect_left(tails, x) # first tail >= x
if k == len(tails):
tails.append(x)
else:
tails[k] = x
return len(tails)
# The actual subsequence: tail_idx + prev, then walk back.
def line(h):
tail_idx, prev = [], [-1] * len(h)
tail_vals = [] # h[tail_idx[k]], kept for bisect
for i, x in enumerate(h):
k = bisect_left(tail_vals, x)
if k > 0:
prev[i] = tail_idx[k - 1]
if k == len(tail_idx):
tail_idx.append(i); tail_vals.append(x)
else:
tail_idx[k] = i; tail_vals[k] = x
out, i = [], tail_idx[-1] if tail_idx else -1
while i != -1:
out.append(h[i]); i = prev[i]
return out[::-1]
print(lis([150, 142, 135, 140, 138, 145, 160, 155]))
print(lis([0, 1, 0, 3, 2, 3]))
print(lis([]), lis([7, 7, 7, 7]), lis([5, 4, 3, 2, 1]))
print(line([150, 142, 135, 140, 138, 145, 160, 155]))
random.seed(42)
a = [random.randrange(10**9) for _ in range(1000000)]
print("1000000 numbers:", lis(a))
Output:
4
4
0 1 1
[135, 138, 145, 155]
1000000 numbers: 1982
Three real bugs
Bug 1: <= in the binary search. Equal values append instead of replacing, so it counts non-decreasing subsequences.
import java.util.*;
public class Main {
static int lis(int[] nums) {
int[] tails = new int[nums.length];
int len = 0;
for (int x : nums) {
int lo = 0, hi = len;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (tails[mid] <= x) lo = mid + 1;
else hi = mid;
}
tails[lo] = x;
if (lo == len) len++;
}
return len;
}
public static void main(String[] args) {
System.out.println(lis(new int[]{7, 7, 7, 7}));
System.out.println(lis(new int[]{1, 3, 3, 5}));
}
}
Output: 4 and 4, instead of 1 and 3.
Bug 2: using Arrays.binarySearch's result directly. When x is missing it returns -(insertion point) - 1; on the empty range that is -1.
import java.util.*;
public class Main {
static int lis(int[] nums) {
int[] tails = new int[nums.length];
int len = 0;
for (int x : nums) {
int i = Arrays.binarySearch(tails, 0, len, x);
tails[i] = x;
if (i == len) len++;
}
return len;
}
public static void main(String[] args) {
System.out.println(lis(new int[]{150, 142, 135, 140, 138, 145, 160, 155}));
}
}
Output:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 8
at Main.lis(Main.java:9)
at Main.main(Main.java:15)
Fix: if (i < 0) i = -(i + 1); (if x is found, replacing a tail with an equal value changes nothing). With the fix the output is 4 4 0 1 1 again.
Bug 3: returning tails as the line.
import java.util.*;
public class Main {
static int[] lis(int[] nums) {
int[] tails = new int[nums.length];
int len = 0;
for (int x : nums) {
int lo = 0, hi = len;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (tails[mid] < x) lo = mid + 1;
else hi = mid;
}
tails[lo] = x;
if (lo == len) len++;
}
return Arrays.copyOf(tails, len);
}
public static void main(String[] args) {
System.out.println(Arrays.toString(lis(new int[]{140, 145, 150, 135})));
}
}
Output: [135, 145, 150]. But 135 is the last student, after 145 and 150: not a subsequence at all. The length (3) is right; the contents are not. Use tailIdx + prev.
Complexity
| Approach | Time | Space | Big input |
|---|---|---|---|
| Keep or skip (every subsequence) | O(2^n) | O(n) stack | 60 students: Time Limit Exceeded |
| dp[i] over every j | O(n²) | O(n) | 200,000: Time Limit Exceeded |
| tails + binary search | O(n log n) | O(n) | 1,000,000 in ~58 ms |
| + tailIdx and prev (the line) | O(n log n) | O(n) |
A million numbers: about n log₂ n ≈ 20 million steps, instead of n² / 2 = 500 billion.
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| Keep or skip every number | Time Limit Exceeded (60 students) | 2^n subsequences |
DP, then tails |
O(n²) DP for n = 200,000 |
Time Limit Exceeded | 20 billion comparisons | tails + binary search |
tails[mid] <= x |
4 instead of 1 on [7, 7, 7, 7] |
equal values appended | tails[mid] < x (lower bound) |
Arrays.binarySearch result as index |
ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 8 |
returns -(insertion point) - 1 |
if (i < 0) i = -(i + 1) |
Printing tails as the LIS |
[135, 145, 150] (not a subsequence) |
tails mixes lines | tailIdx + prev, walk back |
Answer = dp[n - 1] in the O(n²) DP |
too small when the LIS ends earlier | the line can end anywhere | max(dp[i]) |
Mini project: the class photo planner
Read the heights of a class (in roll-number order) and print: how many students can stay, which ones (by roll number and height), and which ones must step out. Extension: allow equal heights to stand next to each other (non-decreasing: search for the first tail > x), and compare the two answers.
Practice
1. Longest Increasing Subsequence (LeetCode 300). Exactly this episode.
Solution
The tails solution above, in any of the three languages. O(n log n) time, O(n) space.
2. Number of Longest Increasing Subsequences (LeetCode 673). How many different LIS are there?
Solution
The O(n²) DP, plus count[i] = number of best lines ending at i. A longer line resets the count; an equally long one adds to it.
from bisect import bisect_left
# Number of LIS (LeetCode 673): O(n²) DP with a count of best lines ending at each i.
def find_number_of_lis(nums):
n = len(nums)
length, count = [1] * n, [1] * n
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
if length[j] + 1 > length[i]:
length[i], count[i] = length[j] + 1, count[j]
elif length[j] + 1 == length[i]:
count[i] += count[j]
best = max(length, default=0)
return sum(c for l, c in zip(length, count) if l == best)
print(find_number_of_lis([1, 3, 5, 4, 7]), find_number_of_lis([2, 2, 2, 2, 2]))
2 5
3. Russian Doll Envelopes (LeetCode 354). Envelope (w, h) fits in another if both width and height are strictly smaller. Most envelopes nested?
Solution
Sort by width up and, for equal widths, height down (so two envelopes of the same width can't both be picked), then LIS on the heights.
from bisect import bisect_left
# Russian Doll Envelopes (LeetCode 354): sort by width up, and by height DOWN for equal widths,
# so two envelopes of the same width can never both be in the chain. Then LIS on the heights.
def max_envelopes(envelopes):
envelopes.sort(key=lambda e: (e[0], -e[1]))
tails = []
for _, h in envelopes:
k = bisect_left(tails, h)
if k == len(tails):
tails.append(h)
else:
tails[k] = h
return len(tails)
print(max_envelopes([[5, 4], [6, 4], [6, 7], [2, 3]]), max_envelopes([[1, 1], [1, 1], [1, 1]]))
3 1
4. Largest Divisible Subset (LeetCode 368). The largest subset where every pair divides one way or the other.
Solution
Sort, then the O(n²) LIS DP with "nums[j] divides nums[i]" instead of <, and prev to rebuild the subset.
# Largest Divisible Subset (LeetCode 368): sort, then the O(n²) LIS DP with "divides" instead of "<".
def largest_divisible_subset(nums):
nums.sort()
n = len(nums)
dp, prev = [1] * n, [-1] * n
for i in range(n):
for j in range(i):
if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
dp[i], prev[i] = dp[j] + 1, j
i = max(range(n), key=lambda k: dp[k]) if n else -1
out = []
while i != -1:
out.append(nums[i]); i = prev[i]
return out[::-1]
print(largest_divisible_subset([1, 2, 3]), largest_divisible_subset([1, 2, 4, 8]))
[1, 2] [1, 2, 4, 8]
5. Fewest students out (non-decreasing). If equal heights may stand together, how many must step out?
Solution
n minus the longest non-decreasing subsequence: use the upper bound (bisect_right, first tail > x).
from bisect import bisect_right
# Fewest students to send out so the rest are NON-DECREASING (equal heights allowed):
# n minus the longest non-decreasing subsequence, found with bisect_right (first tail > x).
def min_removals(h):
tails = []
for x in h:
k = bisect_right(tails, x)
if k == len(tails):
tails.append(x)
else:
tails[k] = x
return len(h) - len(tails)
print(min_removals([150, 142, 135, 140, 138, 145, 160, 155]), min_removals([140, 140, 135, 150]))
4 1
Quick quiz
nums = [4, 10, 4, 3, 8, 9]. Length of the LIS? A) 2 B) 3 C) 4 D) 5
Answer
B) 3. tails: [4] → [4, 10] → [4, 10] → [3, 10] → [3, 8] → [3, 8, 9]. For example 4, 8, 9.
Interview questions
- Subsequence vs subarray? A subsequence keeps the order but may skip elements; a subarray is contiguous.
- State and recurrence of the O(n²) DP?
dp[i] = 1 + max(dp[j])overj < iwithnums[j] < nums[i]; answermax(dp). - What does
tails[k]mean, and why is it sorted? The smallest end of an increasing subsequence of lengthk + 1; a longer one contains a shorter one ending lower. - Lower bound or upper bound? Lower bound (first
≥ x) for strictly increasing; upper bound (first> x) for non-decreasing. - Is
tailsthe LIS? No; only its length is right. Rebuild withtailIdxandprev. - Complexity?
O(n log n)time,O(n)space. - Where else does LIS appear? Russian doll envelopes, box stacking, minimum deletions to sort, the longest chain of pairs, patience sorting.
Glossary
| Term | Meaning |
|---|---|
| Subsequence | Elements kept in their original order, gaps allowed |
| Subarray | A contiguous block of the array |
| Strictly increasing | Each element bigger than the previous (<) |
| Non-decreasing | Each element at least the previous (≤) |
| LIS | Longest (strictly) increasing subsequence |
| Brute force | Trying every possibility (2^n subsequences) |
| State | The numbers that describe a sub-problem |
| dp[i] | Longest increasing subsequence ending at i |
| tails[k] | Smallest last value of an increasing subsequence of length k + 1 |
| Binary search | Halving a sorted range: O(log n) |
| Lower bound | First position with value ≥ x |
| Upper bound | First position with value > x |
| Insertion point | Where x would go to keep the array sorted |
| Patience sorting | The card game behind the tails method |
Summary
- LIS: delete elements, keep the order, the rest strictly increasing; return the longest length.
- Keep-or-skip recursion is right but
O(2^n);dp[i](longest ending ati) isO(n²): fine for thousands, too slow for 200,000. - Only a line's last value matters:
tails[k]= smallest end of lengthk + 1, always sorted. - For each
x: lower bound intails, replace or append. Length oftails= the answer.O(n log n)time,O(n)space. tailsis not the line:tailIdx+prevrebuild it. Next episode: longest common subsequence, two strings and a 2D table.