Free Timed practice lessonsTimed practice · Stage 1 · Timed set 2 · Step 4

The longest climb

Find the length of the longest strictly increasing run of values (in order, not necessarily neighbours) by keeping the best tail for each length and searching it. About 18 minutes.

Tails of the climbs

Pick values from the list left to right (skipping some is allowed) so that each is bigger than the one before. How long can such a climb be? You can track the best possible ending of a climb for each length: the smallest value that a climb of that length can end on. A smaller ending is always better, since it is easier to extend.

Keep these endings in a list called tails. Tails is always sorted, so a new value finds its place with binary search.

Tails: the smallest ending for each climb length.

Sorted always: so each new value is placed by binary search.

In code

from bisect import bisect_left
tails = [2, 5, 7]
pos = bisect_left(tails, 6)   # 2

Values 4, 10, 4, 3, 8, 9. The tails after each value.

leftright

4 starts a climb of length 1. Tails: 4.

Move 1 of 5

Extend or replace

For each new value, find the first tail that is at least as large. If every tail is smaller, the value extends the longest climb, so append it. Otherwise it can replace that tail, giving a climb of the same length a smaller ending.

The list of tails is not itself a climb you can read off, but its length is always the longest climb so far.

Bigger than all tails: append: the climb grows.

Otherwise: replace the first tail at least as big.

Quick check

Tails are 2, 5, 9. The next value is 6. What happens?

A6 replaces 9, the first tail at least as big
B6 is appended
CIt's ignored

Show the answer

6 replaces 9, the first tail at least as big. A climb of length 3 can now end on 6, which is a better ending than 9.

Your problem

Longest climb

nums is a list of whole numbers. A climb is a choice of some values from the list, taken in their original order (skipping is allowed), where each chosen value is strictly bigger than the previous one. Return the length of the longest climb.

Example

nums = [10, 9, 2, 5, 3, 7, 101, 18] → 4

0 ≤ length ≤ 100,000 · −1,000,000,000 ≤ value ≤ 1,000,000,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.