Find the Highest Altitude
The key idea
The altitude at each point is the running prefix sum of the gain array, starting from 0. Track that running sum as you scan and remember the largest value it ever reaches. You never need to store all altitudes at once.
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 to 0.
You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i and i + 1 for all (0 <= i < n). Return the highest altitude of a point.
Constraints
- n == gain.length
- 1 <= n <= 100
- -100 <= gain[i] <= 100
Examples
Input: gain=[-5,1,5,0,-7]
Output: 1
Input: gain=[-4,-3,-2,-1,4,3,2]
Output: 0
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization