#1732
Find the Highest Altitude
Easy Running sum
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
A biker starts at altitude 0. gain[i] is the change in altitude between point i and point i + 1. Return the highest altitude reached.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the altitude after each step is a running total of the gains; what's the highest point?
Why this works: keep the running total and its maximum; the start (0) counts too.
Example: gain = [-5, 1, 5, 0, -7]
altitudes: 0, -5, -4, 1, 1, -6highest = 1
✦Hints open one at a time
The altitude at each point is a prefix sum of the gains.
Don't forget the starting altitude 0 is also a candidate.
↗Approach
Keep a running altitude and the maximum, starting both at 0.
</>Solution (Java)
class Solution {
public int largestAltitude(int[] gain) {
int alt = 0, best = 0; // start point counts
for (int g : gain) {
alt += g;
best = Math.max(best, alt);
}
return best;
}
}!Common mistake
Initialising the maximum to the first gain — if all gains are negative, the answer is 0.
Complexity
- Time: O(n).
- Space: O(1).
