Find the Highest Altitude

Solving tips

The array holds deltas and altitude i is the prefix sum, so carry one running total instead of re-summing (streaming prefix sum).
Track the max as you go in a single O(n) pass, O(1) space; max(0, max(accumulate(gain))) is the idiomatic one-liner.
Seed the max with 0 because the starting altitude counts; with all-negative gains the answer is 0.
Return the maximum altitude reached, not the final altitude, since the peak may occur mid-trip.

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

Tiny bounds — even quadratic passes — but the point of the exercise is the single-pass prefix-sum idea.

Think about it first

Hint 1

The altitude after leg i is a sum of which elements? Write out the sequence of altitudes for the first example.

Hint 2

Do you need to recompute each altitude from scratch, or does altitude i follow from altitude i - 1 in O(1)?

Hint 3

Keep a running sum starting at 0, add each gain in order, and track the maximum value the running sum ever takes — remembering that the start itself counts.

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


class Solution:
    def largestAltitude(self, 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. With n <= 100 it actually passes — the constraints don’t kill it — but it redoes work that grows quadratically and would collapse at realistic sizes.

Approach 2 — Running prefix sum

The insight: consecutive altitudes overlap almost entirely — altitude i is just altitude i - 1 plus gain[i]. This is the prefix sum technique in its streaming form: carry one running total instead of re-summing, and fold the max into the same pass.

from typing import List


class Solution:
    def largestAltitude(self, 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]:

g	altitude	best
— (start)	0	0
-5	-5	0
1	-4	0
5	1	1
0	1	1
-7	-6	1

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 insight: the sequence of altitudes is the sequence of prefix sums, and Python ships a generator for exactly that — itertools.accumulate. Expressing the loop as max over accumulate makes the intent (“highest prefix sum, floored by the start”) read directly.

from itertools import accumulate
from typing import List


class Solution:
    def largestAltitude(self, 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 asymptotics as Approach 2 — this is the idiomatic-Python spelling of the identical algorithm.

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

“Sequence of deltas, question about positions” means prefix sums: one running accumulator turns every position query into O(1) incremental work. Fold whatever aggregate the problem asks for (here a max, elsewhere a count or a hash-map lookup of earlier prefix values) into the same single pass — this is the same running-prefix skeleton that powers Find Pivot Index and subarray-sum problems.