Code Logo

Find the Highest Altitude

Published at24 Jul 2026
Created by
Easy 1 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

Solution Approach

Given an array of altitude changes where gain[i] is the net change between point i and i+1, find the highest altitude reached starting from altitude 0. Simulate the hike by keeping a running altitude that starts at 0. At each step, add the current gain to the running altitude. Track the maximum altitude seen during the entire hike.

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

The starting altitude of 0 counts as a potential maximum. Each gain is accumulated, and the running total is compared against the current maximum. Returns the highest point reached, which could be the starting point if all gains are negative.

Time complexity is O(n), space complexity is 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;
    }
}