Longest Increasing Subsequence

Problem statement. The input is an array $A$ of $n$ integers. Our goal is to return the length of the longest increasing subsequence (LIS) in $A$. (This is LeetCode 300.)

Solution. Here's an $O(n\log n)$-time algorithm: scan $A$, and in the process, update a list ends as shown below. (Note that |ends| refers to the length of ends.)

ALG(A):
  ends = [empty list]
  for a in A:
    binary search for the smallest i such that ends[i] >= a
    if ends is empty or max(ends) < a: i = |ends| + 1
    if i = |ends| + 1:
      append a to ends
    else:
      ends[i] = a
  return ends # answer is |ends|

Correctness (sketch). We claim that ends[k] is the smallest possible last element of any increasing subsequence of length k, within the prefix of A that we've seen so far. For example, suppose ends = [2, 4, 10]. This implies that our current LIS has length 3, and it ends on a 10.

If a = 15, then we can create an LIS of length 4 by appending 15 to the LIS of length 3. The algorithm tracks this by appending 15 to ends.
If a = 1, then we can create an LIS of length 1 by starting at this 1. The algorithm tracks this by replacing the 2 in ends with a 1.
If a = 7, then we can create an LIS of length 3 by appending 7 to the LIS of length 2. This is valid because that LIS ends on ends[2] = 4. The algorithm tracks this by replacing the 10 in ends with a 7.

Notice that ends is always increasing, which allows us to use binary search. For example, ends = [2, 6, 5] is not possible because ends[3] = 5 means that there's an LIS of length 3 that ends on a 5, which implies that there's an LIS of length 2 that ends on something less than 5, so ends[2] cannot be 6.

What to submit. You'll be given a random instance of length 15 using the generate function below. You should submit the list ends generated by the algorithm above.

Practice. Enter an array below or click Generate for a random one. Click Solve to check your answer.

import random

def generate():
    A = []
    for _ in range(15):
        x = random.randint(1, 20)
        while A and x == A[-1]:
            x = random.randint(1, 20)
        A.append(x)
    return A

def solve(A):
    ends = [0] # extra element so ends is 1-indexed
    for a in A:
        i, j = 1, len(ends) - 1
        while i <= j:
            mid = (i + j) // 2
            if ends[mid] >= a:
                j = mid - 1
            else:
                i = mid + 1
        if i == len(ends):
            ends.append(a)
        else:
            ends[i] = a
    return ends[1:] # answer is len(ends) - 1

Extra Credit: Longest Increasing Subsequence