Find the Highest Altitude
Find the Highest Altitude: given the net gain between consecutive points, starting from altitude 0, return the highest altitude reached.
- 1 <= gain.length <= 100
- -100 <= gain[i] <= 100
Intuition
The array holds changes, not positions. Add them up as you go and the running total is the current altitude; track the largest value that total ever reaches. The start at 0 counts as a candidate, which matters when every leg descends.
The tell is 'net change' or 'difference between consecutive' — the values are deltas, and the quantity you actually want is their prefix sum. Once you spot that, this is the same machinery as Running Sum of 1D Array with a maximum tracked alongside.
Approach
Before reading on: the array gives changes, not heights. Work out what the altitude is after three legs, and decide whether the starting point can ever be the answer. Aim for O(n) with O(1) space.
Differences and positions are not the same thing
gain[i] is how much the altitude changes on leg i, so no single entry is an altitude. The altitude after k legs is the sum of the first k gains — a prefix sum. Reading the problem as 'find the maximum of the array' answers a different question entirely, which is the most common misreading here.
One accumulator, one maximum
Keep altitude at 0 and highest at 0. For each gain, add it to altitude and then compare against highest, keeping the larger. One pass, two integers, no array allocation. Because you compare after each addition, every intermediate altitude is considered — not just the final one, which may well be lower than a peak reached in the middle.
Why the initial 0 must seed the maximum
The cyclist starts at altitude 0, and that is a legitimate altitude. If every gain is negative, the highest point of the whole journey is the starting point. Initialising highest = 0 captures that. Initialising it to something like negative infinity, or to gain[0], silently reports a negative peak on an all-downhill route.
Solution & live demo
Common pitfalls
Returning the maximum of the input
return max(gain)
altitude += step highest = max(highest, altitude)
gain holds changes, not altitudes. On [-5,1,5,0,-7] this returns 5, but the highest altitude actually reached is 1.
Not counting the starting altitude
highest = gain[0]
highest = 0
The journey begins at 0, which is a valid altitude. On an all-downhill route like [-4,-3,-2] the correct answer is 0, but seeding from the first gain reports -4.
Returning the final altitude
for step in gain:
altitude += step
return altitudehighest = max(highest, altitude) # inside the loop
The end of the ride is not necessarily its highest point. The maximum must be captured as the walk proceeds, since a mid-journey peak is lost once the descent begins.
Edge cases
Every altitude is below 0, so the answer is the starting altitude, 0.
The altitude rises monotonically and the answer is the final total.
The maximum is reached mid-journey, so comparing at every step is essential.
One addition gives 10, which beats the starting 0.
The peak of 3 is recorded before the descent returns to 0.