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.
from bisect import bisect_left tails = [2, 5, 7] pos = bisect_left(tails, 6) # 2
4 starts a climb of length 1. Tails: 4.
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.
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.
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.
nums = [10, 9, 2, 5, 3, 7, 101, 18] → 4
0 ≤ length ≤ 100,000 · −1,000,000,000 ≤ value ≤ 1,000,000,000