A hiking map gives the height of every square of a region as a grid of integers. A trail steps from a square to one of its four neighbours (up, down, left, right; never diagonally, never off the map), and every step must go strictly uphill. A trail may start anywhere.
Implement longest_climb(heights: list[list[int]]) -> int: the number of squares on the longest trail.
longest_climb([
[9, 9, 4],
[6, 6, 8],
[2, 1, 1],
])
# 4 (1 -> 2 -> 6 -> 9)
longest_climb([
[3, 4, 5],
[3, 2, 6],
[2, 2, 1],
])
# 4 (3 -> 4 -> 5 -> 6)
longest_climb([[7, 7], [7, 7]]) # 1 (flat ground: a trail of one square)
1 <= rows, cols <= 300; heights are in[0, 10^9].- Aim for O(rows·cols·log(rows·cols)) or better. Following every trail from every square is exponential, and a trail can wind through the whole map, so deep recursion will hit Python's limit (about 1,000 frames).
Show hint
The longest trail starting at a square depends only on the longest trails starting at its higher neighbours. If you handle squares from the highest down, those answers are always ready when you need them.