Longest increasing subsequence

The longest increasing subsequence (LIS) of a list is the longest selection of its values, kept in their original order but not necessarily next to each other, in which every value is larger than the one before. In [52, 48, 61, 55, 70, 66, 74, 59] it has length 4: 52, 61, 70 and 74 is one answer, and 48, 55, 66 and 74 is another. It is a classic interview problem because a correct answer is easy to write and slow, and a fast one needs a single observation about which runs are worth keeping. The same idea returns in nesting boxes, chains of pairs and the fewest changes that make a list rise.

Improving months

The problem. A learner sits one mock test a month and writes down the score, scores[0..n − 1]. Choose some of the months, keeping their order, so that every chosen score is strictly higher than the one chosen before it. Return the largest number of months you can choose, and one such list of scores. Limits: 1 ≤ n ≤ 2 × 10⁵ and 0 ≤ scores[i] ≤ 10⁹.

• [52, 48, 61, 55, 70, 66, 74, 59] gives 4, for example with 52, 61, 70 and 74.
• [40, 40, 40] gives 1, because an equal score is not an improvement.
• [90, 80, 70] gives 1, because each month on its own is a run of one.

The brute force, and why it fails at these sizes

Every month is either taken or skipped, and a month can be taken only if its score beats the last score taken. A recursion that tries both choices at every month finds the answer, and the run below counts its calls. When the scores rise every month, every choice is valid, so the calls double with each extra month: 2,047 for ten months and 524,287 for eighteen. Sixty months would take more than 2 × 10¹⁸ calls, and at the limit of 200,000 months the number of calls has 60,207 digits.

"""Improving months by brute force: take or skip every month, and count the calls."""
import math


def longest_by_search(scores):
    """The most months whose scores rise strictly, trying every way to take or skip each month."""
    calls = 0

    def best(i, last):
        # best(i, last): the most months that can still be taken from month i on, above the score `last`.
        nonlocal calls
        calls += 1
        if i == len(scores):
            return 0
        skip = best(i + 1, last)
        if scores[i] > last:
            return max(skip, 1 + best(i + 1, scores[i]))
        return skip

    return best(0, -1), calls  # scores are at least 0, so -1 lies below every score


def months(k):
    return f"{k} month" if k == 1 else f"{k} months"


for scores in ([52, 48, 61, 55, 70, 66, 74, 59], [40, 40, 40], [90, 80, 70]):
    length, calls = longest_by_search(scores)
    print(f"{scores}: {months(length)}, {calls:,} calls")

print()
print("Scores that rise every month are the worst case: every choice of months is a valid one.")
for n in (10, 14, 18):
    length, calls = longest_by_search(list(range(n)))
    print(f"n = {n:2}: {months(length):>9}, {calls:>9,} calls")

# The calls double with every month: 2 ** (n + 1) - 1 for n rising scores.
print(f"n = 60 would make {2 ** 61 - 1:,} calls")
digits = math.floor((200_000 + 1) * math.log10(2)) + 1
print(f"n = 200,000 would make a number of calls with {digits:,} digits")

[52, 48, 61, 55, 70, 66, 74, 59]: 4 months, 180 calls
[40, 40, 40]: 1 month, 10 calls
[90, 80, 70]: 1 month, 10 calls

Scores that rise every month are the worst case: every choice of months is a valid one.
n = 10: 10 months,     2,047 calls
n = 14: 14 months,    32,767 calls
n = 18: 18 months,   524,287 calls
n = 60 would make 2,305,843,009,213,693,951 calls
n = 200,000 would make a number of calls with 60,207 digits

What to notice

• A run needs only its last score to grow. How it got there does not matter, so the best run that ends at a month can be built from the best runs that end at earlier, lower months.
• Among runs of the same length, the one with the lowest last score is the most useful, because every later score that extends any of them also extends that one.

Two methods follow from these points. The quadratic DP computes, for every month, the longest improving run that ends there, by looking back at every earlier lower score. At 200,000 months that is about 2 × 10¹⁰ comparisons, minutes of work even in C++, which manages roughly 10⁸ simple steps a second (the constraints lesson measures it). The tails method keeps one number per length, the smallest last score of an improving run of that length, and places each new score by binary search.

The quadratic DP: the best run that ends at each month Pro: opens with a Pro, Premium or Ultimate pass