Track altitude changes along a route and return the highest altitude reached, starting from sea level.
Problem
You are given an array gain where gain[i] represents the net altitude change between point i and point i + 1 on a biking trip.
You start at altitude 0 (sea level). After each move, your altitude changes by the corresponding value in gain.
Return the highest altitude reached during the trip, including the starting altitude.
Goal
Compute the maximum value among all prefix sums of gain, with the initial altitude 0 included.
Input Format
- An integer array
gainof lengthn. gain[i]is the altitude change from checkpointito checkpointi + 1.
Output Format
- Return a single integer: the maximum altitude reached at any point in the trip.
Constraints
1 <= gain.length <= 1000-1000 <= gain[i] <= 1000- The starting altitude is
0.
Example 1
Input
gain = [-5,1,5,0,-7]
Output
1
Explanation
Starting at 0, the altitude changes are: 0 -> -5 -> -4 -> 1 -> 1 -> -6. The highest altitude reached is 1.
Example 2
Input
gain = [-4,-3,-2,-1,4,3,2]
Output
0
Explanation
The altitude never rises above the starting altitude of 0, so the answer is 0.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.