Typing Class Progress

Mediumdynamic programmingAlso known as Longest Increasing Subsequence

A night-school typing class records each student's speed, in words per minute, at the end of every session. Speeds go up and down: a tired evening, a hard text, a good night's sleep. At the end of term the teacher writes a progress note that quotes some of the sessions, in date order, where each quoted speed is strictly faster than the one quoted before it.

The longer the chain of improving sessions, the more encouraging the note. What is the longest chain she can quote for a student?

Your task

Write longestImprovement(speeds). Return the length of the longest list of sessions you can pick, keeping their original order, where each picked speed is strictly greater than the previous picked speed. The picked sessions do not need to be next to each other.

An empty record gives 0. Equal speeds do not count as an improvement.

longestImprovement(speeds: int[]) → int

Examples

Example 1

Input

speeds = [42, 38, 45, 40, 47, 41, 43, 50]

Output

Why

Quote 38, 40, 41, 43, 50. Starting with the first session, 42, gets you at most 42, 45, 47, 50, which is 4. The best chain starts with a dip.

Example 2

Input

speeds = [30, 30, 30]

Output

Why

Every session is the same speed. A chain needs each speed to be strictly faster, so the best is one session on its own.

Constraints

0 ≤ speeds.length ≤ 2,500
0 ≤ speeds[i] ≤ 200

Start with brute force

Try every subset of sessions, check whether it is strictly increasing, and keep the longest. With 2,500 sessions there are 2²⁵⁰⁰ subsets. Even 40 sessions means about a trillion.

Two quick shortcuts are wrong. The longest run of consecutive rising sessions misses chains that skip bad days. Greedily taking every session that beats the last one you took fails on [1, 9, 2, 3, 4]: it takes 1, 9 and gets stuck.

Hints

0 of 4 shown

Hint 1
Take the session with speed 43 in the first example. Suppose the chain must end at 43. Which earlier sessions could come just before it?
Hint 2
Any earlier session with a smaller speed: 42, 38, 40 or 41. The best chain ending at 43 is one longer than the best chain ending at any of those. So it helps to know, for every session, the best chain that ends exactly there.
Hint 3
Let best[i] be the length of the longest improving chain that ends at session i. Every session alone is a chain of 1. Then best[i] = 1 + max(best[j]) over earlier j with speeds[j] < speeds[i].
Hint 4
Fill best from left to right with a double loop: for each i, scan every j < i. The answer is the largest value anywhere in best, not just the last one, because the chain can end at any session.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

A chain has a last session. Fix it, and the question gets small: the best chain ending at i is session i added to the best chain ending at some earlier, slower session. Compute that for every i from left to right.

Trace [42, 38, 45, 40, 47, 41, 43, 50]:

42: nothing before it. best = 1.
38: 42 is not slower. best = 1.
45: 42 and 38 are slower, both with 1. best = 2.
40: only 38 is slower. best = 2.
47: the slower ones have at most 2 (45 or 40). best = 3.
41: slower are 38 (1) and 40 (2). best = 3.
43: slower are 42, 38, 40, 41; the best of them is 41 with 3. best = 4.
50: everything before is slower; the best is 43 with 4. best = 5.

The answer is the largest value, 5. With 2,500 sessions the double loop does about 3 million comparisons, which is quick. A cleverer method with binary search gets O(n log n); it is covered in this lesson.

Reference solution

function longestImprovement(speeds) {
  const n = speeds.length;
  const best = new Array(n).fill(1); // best[i] = longest chain ending at session i
  let answer = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      // session j can come right before session i if it was slower
      if (speeds[j] < speeds[i] && best[j] + 1 > best[i]) best[i] = best[j] + 1;
    }
    answer = Math.max(answer, best[i]);
  }
  return answer;
}

def longest_improvement(speeds):
    n = len(speeds)
    best = [1] * n  # best[i] = longest chain ending at session i
    for i in range(n):
        for j in range(i):
            # session j can come right before session i if it was slower
            if speeds[j] < speeds[i] and best[j] + 1 > best[i]:
                best[i] = best[j] + 1
    return max(best, default=0)

TimeO(n²)For each session, scan every earlier session once.

SpaceO(n)One chain length per session.

Learn the idea: Longest Increasing Subsequence 1D Dynamic Programming

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code