A warehouse posts lot quality scores in the order pallets arrived — not sorted, not de-duplicated. QA wants the longest chain they can still print as a strictly improving sample: each hop must go to a strictly higher score. Skipping lots is allowed. Adjacent-on-the-dock is not required. The intern who heard “increasing” scanned for the longest contiguous run. That answers a different question.

Longest Increasing Subsequence asks for the length of a strictly increasing subsequence. An array already gives a[i] for free. Order is kept. Holes are legal. This is not a subarray: Maximum Subarray forbids holes. A contiguous increasing run is one scan that restarts on a drop — also not this prompt.

This is an interview writeup, not the patience lecture. The LIS post owns the n log n proof, why tails is not the path, and recovering hops. Here we write the honest O(n²) table, then the tails pass the board actually wants.

The problem

Given an int[] nums, return the length of the longest strictly increasing subsequence. You may skip indexes. You may not reorder. Equals do not extend. Empty input is length 0. A singleton is 1.

nums = [5, 6, 1, 7, 2, 8]  →  4    e.g. [5, 6, 7, 8]
nums = [1, 2, 3]           →  3    the whole array
nums = [3, 2, 1]           →  1    every pick is a singleton
nums = [7]                 →  1

Note: Subsequence, not subarray. On [5, 6, 1, 7, 2, 8] the longest contiguous increase is length 2 ([5, 6]). The subsequence length is 4. If they wanted a contiguous run, say so and write a restart scan — do not run LIS and over-count.

Nested predecessors are the honest DP

At index i, any increasing subsequence that ends at i is nums[i] alone, or some increasing subsequence that ended at an earlier j with nums[j] < nums[i], plus nums[i]. Enumerating every subset is O(2^n). The honest first table scans every j < i. Correct. Quadratic.

int lisQuadratic(int[] nums) {
    int n = nums.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 (nums[j] < nums[i]) {
                bestEndingHere[i] = Math.max(bestEndingHere[i], bestEndingHere[j] + 1);
            }
        }
        best = Math.max(best, bestEndingHere[i]);
    }
    return best;
}

At n = 20 this is a rounding error. At a dock of thousands of lots you paid every pair for a question a tails array answers with one lower bound per value: for each length, what is the smallest tail we have seen? Tiny n can keep this table — the recurrence stays obvious. Do not skip it on the board and jump to binary search with no invariant.

You do not need every bestEndingHere[j]. You need, for each length k, the smallest tail of any increasing subsequence of that length. That tails prefix stays sorted. Place each x with a lower bound: append if x is a new longest, otherwise replace the first tail that is >= x. Length is the live size of tails, not the values in the row.

The LIS tutorial owns why this is patience sorting, why the row is not guaranteed to be a subsequence, and how predecessor indexes recover the hops. Do not re-prove it here. Write the placement and stop.

x     tails after the placement
5     [5]
6     [5, 6]
1     [1, 6]
7     [1, 6, 7]
2     [1, 2, 7]
8     [1, 2, 7, 8]

size = 4

[1, 2, 7, 8] is not a subsequence: 7 arrived before 2. Length is still 4. Do not return tails and call it the sample chain.

The Java is that placement. Search only the live prefix; the rest of the buffer is garbage:

int lengthOfLIS(int[] nums) {
    int n = nums.length;
    if (n == 0) {
        return 0;
    }
    int[] tails = new int[n];
    int size = 0;
    for (int x : nums) {
        int i = Arrays.binarySearch(tails, 0, size, x);
        if (i < 0) {
            i = -(i + 1);
        }
        tails[i] = x;
        if (i == size) {
            size++;
        }
    }
    return size;
}

Quadratic DP is O(n²) time, O(n) extra — every j < i. Tails is O(n log n) time, O(n) extra — one lower bound per element. Empty is 0. There is no JDK Arrays.lis.

Note: Do not print tails as the sequence. Length is size. A hit on binarySearch means x already sits on a pile — replace in place; strictly increasing does not grow. Non-decreasing needs a different bound; the tutorial names it. Do not flip < in the quadratic table and keep this lower-bound replace.

What interviewers usually poke next

  • Recover the path. Predecessor indexes in the same pass. The LIS post already walks prev. Length-only Java does not remember hops.
  • Non-decreasing. Equals must extend. Change quadratic < to <=, and change the tails search to an upper bound. Pick a spec; do not mix the two.
  • Contiguous run. Longest increasing subarray is one scan: extend while nums[i] > nums[i - 1], else restart. LIS will skip and over-count that spec.
  • Count of LIS, or the lexicographically smallest among many. Extra state. Out of scope unless they switch.
  • LCS against a sorted unique copy. Correct cousin, slower default. Do not rebuild an LCS grid to avoid writing tails.

You are done with this problem when you can say, out loud, why this is not a subarray, why the nested j table is correct, and why the board answer is a tails size rather than every pair of indexes.