Find the Highest Altitude

Problem

A cyclist starts a trip at altitude 0. The trip consists of n legs; you are given an integer array gain of length n, where gain[i] is the net change in altitude during leg i. After leg i the cyclist is at altitude gain[0] + gain[1] + ... + gain[i].

Return the highest altitude the cyclist ever reaches, including the starting altitude 0.

Examples

• gain = [-5,1,5,0,-7] → 1 — altitudes visited are 0, -5, -4, 1, 1, -6; the maximum is 1.
• gain = [-4,-3,-2,-1,4,3,2] → 0 — every prefix sum is negative, so the start (0) is the highest point.
• gain = [2,2,-3,4] → 5 — altitudes are 0, 2, 4, 1, 5; the maximum is 5.

Constraints

• 1 <= len(gain) <= 100
• -100 <= gain[i] <= 100

The bounds are small enough that a quadratic solution passes, but the intended approach is the single-pass prefix sum.

Think about it first

TL;DR

Running prefix sum, track the max — O(n) time, O(1) space.

Approach 1 — Brute force

Compute each visited altitude independently: the altitude after leg i is the sum of the first i + 1 gains, so re-sum that prefix from scratch for every i and take the maximum (seeding with the starting altitude 0).

from typing import List


def largestAltitude(gain: List[int]) -> int:
    best = 0  # the starting altitude counts
    for i in range(len(gain)):
        altitude = sum(gain[:i + 1])
        best = max(best, altitude)
    return best

Complexity: O(n^2) time (prefix i costs i + 1 additions), O(n) space for the slices. It passes at n <= 100, but it recomputes each prefix from scratch and does not scale.

Approach 2 — Running prefix sum

Consecutive altitudes differ by a single term: altitude i equals altitude i - 1 plus gain[i]. Carry one running total instead of re-summing each prefix, and take the max in the same pass.

from typing import List


def largestAltitude(gain: List[int]) -> int:
    best = 0
    altitude = 0
    for g in gain:
        altitude += g
        best = max(best, altitude)
    return best

Walkthrough on gain = [-5,1,5,0,-7]:

Return 1, matching the example. On [-4,-3,-2,-1,4,3,2] the running altitude never rises above 0, so best stays at its seed and the answer is 0.

Complexity: O(n) time, O(1) extra space.

Approach 3 — itertools.accumulate

The sequence of altitudes is the sequence of prefix sums, and itertools.accumulate produces exactly that. Writing the loop as max over accumulate states the intent directly: the highest prefix sum, floored by the starting altitude.

from itertools import accumulate
from typing import List


def largestAltitude(gain: List[int]) -> int:
    return max(0, max(accumulate(gain)))

Walkthrough on gain = [2,2,-3,4]:

• accumulate(gain) yields 2, 4, 1, 5 — the altitudes after each leg.
• Inner max → 5; outer max(0, 5) → 5 (the outer max is what re-admits the starting altitude, which matters when all prefixes are negative).

Complexity: O(n) time, O(1) extra space (accumulate is lazy). Same algorithm as Approach 2, written idiomatically.

Common pitfalls

• Forgetting that the starting altitude 0 counts: with all-negative prefixes (example 2) the answer is 0, not the largest prefix sum. Seed best = 0 or wrap with max(0, ...).
• Returning the final altitude instead of the maximum altitude — the cyclist may peak mid-trip and descend.
• Comparing best before adding g (or after, inconsistently) — update the altitude first, then compare, or you evaluate each leg’s starting point twice and its endpoint never.
• Reading gain[i] as the altitude at point i rather than the change during leg i — the array is deltas, not positions.

Pattern takeaway

A sequence of deltas with a question about positions points to prefix sums: one running accumulator turns each position query into O(1) incremental work. Fold whatever aggregate the problem needs (here a max, elsewhere a count or a hash-map lookup of earlier prefix values) into the same pass. This is the running-prefix skeleton behind Find Pivot Index and subarray-sum problems.