Problem Description

You are given an integer array called gain of length n where gain[i] represents the net gain in altitude between points i and i + 1 on a bike trip. The initial altitude before the trip is 0. Your task is to return the highest altitude reached during the trip.

• The trip starts at altitude 0.
• Each element in gain represents the change in altitude from the previous point.
• You need to find the maximum altitude at any point (including the starting point).

Thought Process

The problem is about tracking altitude changes as we move through the gain array. At each step, we add the current gain to the previous altitude to get the new altitude. We want to keep track of the highest altitude we reach as we go.

A brute-force approach would be to generate all possible altitude values step by step and then find the maximum. But since the altitude at each step only depends on the sum of gains up to that point, we can simply keep a running sum and update the maximum whenever the new altitude is higher.

This is similar to keeping track of your cumulative score in a game and noting the highest score you reach at any point.

Solution Approach

We solve this problem efficiently by iterating through the gain array once, keeping track of the current altitude and the maximum altitude seen so far.

1. Initialize two variables: current_altitude = 0 and max_altitude = 0.
2. For each element g in gain:
   • Add g to current_altitude.
   • If current_altitude is greater than max_altitude, update max_altitude.
3. After processing all elements, max_altitude holds the highest altitude reached.

This approach is efficient because we only need a single pass through the array and constant extra space.

Example Walkthrough

Let's walk through an example with gain = [-5, 1, 5, 0, -7].

• Start at altitude 0 (initial).
• After first gain (-5): altitude = 0 + (-5) = -5
• After second gain (1): altitude = -5 + 1 = -4
• After third gain (5): altitude = -4 + 5 = 1
• After fourth gain (0): altitude = 1 + 0 = 1
• After fifth gain (-7): altitude = 1 + (-7) = -6

The altitudes at each point are: 0, -5, -4, 1, 1, -6. The highest is 1.

Time and Space Complexity

• Brute-force approach: If we generated all altitude values in a separate array and then found the max, it would still be O(n) time and O(n) space.
• Optimized approach: We only need to iterate once through gain and keep two variables. This gives us O(n) time complexity and O(1) space complexity, where n is the length of gain.

Summary

The solution involves a simple running sum to track the current altitude and a variable to record the maximum seen so far. By updating these as we iterate through the gain array, we efficiently determine the highest altitude reached. This approach is both time and space optimal, and demonstrates the power of cumulative tracking in sequential problems.

Code Implementation

class Solution:
    def largestAltitude(self, gain):
        max_altitude = 0
        current_altitude = 0
        for g in gain:
            current_altitude += g
            if current_altitude > max_altitude:
                max_altitude = current_altitude
        return max_altitude
      

class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        int maxAltitude = 0;
        int current = 0;
        for (int g : gain) {
            current += g;
            if (current > maxAltitude)
                maxAltitude = current;
        }
        return maxAltitude;
    }
};
      

class Solution {
    public int largestAltitude(int[] gain) {
        int maxAltitude = 0;
        int current = 0;
        for (int g : gain) {
            current += g;
            if (current > maxAltitude)
                maxAltitude = current;
        }
        return maxAltitude;
    }
}
      

var largestAltitude = function(gain) {
    let maxAltitude = 0;
    let current = 0;
    for (let g of gain) {
        current += g;
        if (current > maxAltitude)
            maxAltitude = current;
    }
    return maxAltitude;
};