SyntaxPilot
Courses/DSA and Coding Problems/Lesson 66
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 66 of 90

Longest increasing subsequence in O(n log n)

queued

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. n elements have 2^n subsequences.
  • State: the few numbers that describe a sub-problem. For the recursion: (i, last kept value); for the DP: i alone.
  • 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 + 1 seen 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 x would go to keep an array sorted; Arrays.binarySearch returns -(insertion point) - 1 when x is 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

  1. State: dp[i] = length of the longest increasing subsequence that ends exactly at i.
  2. Alone: dp[i] = 1.
  3. Extend: for every j < i with nums[j] < nums[i], dp[i] = max(dp[i], dp[j] + 1).
  4. Answer: max(dp[i]) over all i (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 length k + 1.
  • tails is always sorted: a line of length k + 2 contains a line of length k + 1 that ends lower.
  • For each new x: binary search the first tail ≥ x (lower bound). Replace it with x (same length, lower end); if there is none, append x (a longer line). The answer is the length of tails.

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.

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

  1. Subsequence vs subarray? A subsequence keeps the order but may skip elements; a subarray is contiguous.
  2. State and recurrence of the O(n²) DP? dp[i] = 1 + max(dp[j]) over j < i with nums[j] < nums[i]; answer max(dp).
  3. What does tails[k] mean, and why is it sorted? The smallest end of an increasing subsequence of length k + 1; a longer one contains a shorter one ending lower.
  4. Lower bound or upper bound? Lower bound (first ≥ x) for strictly increasing; upper bound (first > x) for non-decreasing.
  5. Is tails the LIS? No; only its length is right. Rebuild with tailIdx and prev.
  6. Complexity? O(n log n) time, O(n) space.
  7. 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 at i) is O(n²): fine for thousands, too slow for 200,000.
  • Only a line's last value matters: tails[k] = smallest end of length k + 1, always sorted.
  • For each x: lower bound in tails, replace or append. Length of tails = the answer. O(n log n) time, O(n) space.
  • tails is not the line: tailIdx + prev rebuild it. Next episode: longest common subsequence, two strings and a 2D table.