The rising traverse

A route setter has bolted holds along a climbing wall and wants the longest route that never drops. The holds are fixed; only the choice of which to use is open.

The problem

The holds are listed left to right along the wall, and each has a height in centimetres above the mats. A rising traverse uses some of the holds in that left-to-right order — the climber always moves rightward and may skip as many holds as they like — and each hold used must be strictly higher than the one before it. Two holds at the same height cannot follow each other, because the climber has to gain something.

Report the number of holds on the longest rising traverse. A route of one hold is a route.

Input. heights — a non-empty list of integers, the height of each hold in centimetres, in wall order from left to right.

Output. The number of holds in the longest strictly rising subsequence.

Example.

heights = [120, 45, 130, 90, 100, 160, 95]   ->  4

The route 45, 90, 100, 160 uses four holds. Starting at 120 gives only 120, 130, 160, three holds — the tall first hold is a trap.

A second example, where the wall only ever drops:

heights = [200, 180, 150, 90]   ->  1

No hold is higher than one to its left, so every route is a single hold.

Constraints.

• 1 <= len(heights) <= 2500
• 0 <= heights[i] <= 10^4

Hints

Approach

Brute force

Test every subset of holds for rising order and keep the longest: 2ⁿ subsets, so 2²⁵⁰⁰ at the top of the constraints. Even for 30 holds that is a billion checks.

The insight

Every rising traverse ends on exactly one hold, so ask for the longest traverse ending at each hold — and that answer is one more than the best answer among strictly lower holds to its left.

The route ending at hold i, minus hold i, is a rising route ending at some earlier lower hold j. So longest[i] = 1 + max(longest[j]) over every j < i with heights[j] < heights[i], or 1 if no such j exists. Each entry depends only on entries already computed, so a single left-to-right pass fills the table, and the answer is the largest entry — not the last one, because the longest route need not reach the right-hand end.

Algorithm

1. Make a table longest, one entry per hold, all set to 1.
2. For each hold i left to right, scan every earlier hold j.
3. If heights[j] < heights[i], take longest[i] = max(longest[i], longest[j] + 1).
4. Return the largest value in longest.

Complexity

Time O(n²) — every hold scans everything to its left, about 3·10⁶ comparisons at n = 2500. Space O(n) for the table. Keeping a list of the smallest possible tail height for each route length and placing each hold with a binary search gets the same number in O(n log n), which is what you would reach for at 10⁵ holds.

Solution

"""The rising traverse — longest strictly increasing subsequence of hold heights."""


def solve(heights):
    if not heights:
        return 0
    # longest[i] = holds on the best rising traverse that FINISHES on hold i.
    # Every such traverse minus its last hold is a shorter one ending lower.
    longest = [1] * len(heights)
    for i in range(1, len(heights)):
        for j in range(i):
            if heights[j] < heights[i]:
                longest[i] = max(longest[i], longest[j] + 1)
    return max(longest)

TESTS = [
    (([120, 45, 130, 90, 100, 160, 95],), 4),
    (([200, 180, 150, 90],), 1),
    (([70, 70, 70],), 1),
    (([10, 20, 30, 40],), 4),
    (([55],), 1),
    (([30, 10, 40, 20, 50, 25, 60],), 4),
    ((list(range(2500)),), 2500),
]

Pitfalls

• Using <= in the comparison. Equal heights then chain, and a wall of [70, 70, 70] reports 3 rising holds when the climber has gained nothing.
• Returning longest[-1]. That is the longest route ending on the last hold, not the longest route: the example returns 2 instead of 4.
• Initialising the table to 0. A hold with no lower hold to its left keeps a 0, and the whole descending wall reports 0 rather than 1.

Variants

• Zigzag border — the same subsequence scan with an alternating condition, which collapses to two rolling counters.
• The hive scale — the contiguous cousin, where runs cannot skip and the whole scan drops to O(n).