Find the Highest Altitude
Problem
There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.
gain = [-5, 1, 5, 0, -7]1def highest_altitude(gain):
alt = best = 0
for g in gain:
alt += g
if alt > best: best = alt
return bestfunction highestAltitude(gain) {
let alt = 0, best = 0;
for (const g of gain) {
alt += g;
if (alt > best) best = alt;
}
return best;
}class Solution {
public int highestAltitude(int[] gain) {
int alt = 0, best = 0;
for (int g : gain) {
alt += g;
if (alt > best) best = alt;
}
return best;
}
}int highestAltitude(vector<int>& gain) {
int alt = 0, best = 0;
for (int g : gain) {
alt += g;
if (alt > best) best = alt;
}
return best;
}Explanation
The biker starts at altitude 0, and each gain[i] tells how much the altitude changes on the next step. The actual altitude at any point is just the running sum of the gains so far, and we want the highest such altitude.
So we keep alt as the running total and best as the maximum altitude seen. Both start at 0 to include the starting point. Each step we add the gain to alt and update best if alt is higher.
This is a tiny prefix-sum with a max tracker — no need to store all altitudes, just the running value and the best one.
Example: gain = [-5,1,5,0,-7]. Altitudes are 0, -5, -4, 1, 1, -6. The highest is 1, so the answer is 1.
One pass over the array with two variables gives an O(n) time, O(1) space solution.