Find the Highest Altitude
Easy · Prefix Sums · Array · Prefix Sum
Problem
A cyclist rides through n + 1 points numbered 0 to n, starting at point 0 at altitude 0. You are given an integer array gain of length n, where gain[i] is the net change in altitude from point i to point i + 1 (positive is uphill, negative is downhill).
Return the highest altitude reached at any point of the ride. The starting point counts, so the answer is never below 0.
Examples
Input: gain = [-5, 1, 5, 0, -7] Output: 1
The altitudes are 0, -5, -4, 1, 1, -6; the highest is 1.
Input: gain = [-4, -3, -2, -1, 4, 3, 2] Output: 0
The altitudes are 0, -4, -7, -9, -10, -6, -3, -1: nothing beats the start.
Input: gain = [2, 3, -1] Output: 5
The altitudes are 0, 2, 5, 4.
Constraints
- 1 <= len(gain) <= 10^4
- -100 <= gain[i] <= 100
Approaches
- Build every altitude — time O(n), space O(n)
Follow-up
What is the largest climb from any point to a later, higher one? And at which point is the top first reached?
Related problems
Start free on Cariara · Coding problems · System design studio
