Code Logo

Find the Highest Altitude

Published at24 Jul 2026
Created by
Easy 0 views
Like0

There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts at altitude 0. You are given an integer array gain of length n where gain[i] is the net gain in altitude between point i and point i+1. Return the highest altitude reached.

This is a simple prefix sum problem: compute the cumulative altitude at each step. The altitude after i steps is the sum of gains[0..i-1]. Track the maximum altitude encountered. Since the biker starts at 0, the maximum is at least 0.

The DP aspect is tracking the cumulative sum state and the maximum-so-far state. Time is O(n) with O(1) extra space. The altitude values can be negative (going downhill) but the maximum altitude is the highest point reached.

Edge cases include empty gain array (return 0), all negative gains (return 0, starting altitude), and a single large positive gain.

This problem demonstrates the simplest form of prefix sum DP: iteratively adding gains while tracking a running maximum. The state is just the current altitude and the best seen so far. This pattern appears in stock profit tracking and cumulative statistics.

The cumulative altitude is simply the running sum of gains starting from 0. This is the simplest prefix sum DP problem. Each step adds the current gain to the running total, and we compare with the best seen so far. The maximum altitude can occur at any point along the journey.

Example Input & Output

Example 1
Input
[-1]
Output
0
Explanation

Single -1, max=0.

Example 2
Input
[]
Output
0
Explanation

No gains, max=0.

Example 3
Input
[-4,-3,-2,-1,4,3,2]
Output
0
Explanation

All altitudes <=0, max=0.

Example 4
Input
[1,2,3,4]
Output
10
Explanation

Sum=10, max=10.

Example 5
Input
[-5,1,5,0,-7]
Output
1
Explanation

Altitudes: -5,-4,1,1,-6. Max=1.

Algorithm Flow

Recommendation Algorithm Flow for Find the Highest Altitude
Recommendation Algorithm Flow for Find the Highest Altitude

Solution Approach

Compute prefix sums cumulatively, track max value. Return max.

function solution(gain) {
  var maxAlt = 0, cur = 0;
  for (var i = 0; i < gain.length; i++) {
    cur += gain[i];
    if (cur > maxAlt) maxAlt = cur;
  }
  return maxAlt;
}

Time O(n), Space O(1).

Best Answers

java
class Solution {
    public int solution(int[] gain) {
        int maxAlt = 0, cur = 0;
        for (int g : gain) {
            cur += g;
            if (cur > maxAlt) maxAlt = cur;
        }
        return maxAlt;
    }
}