Problem Statement

A bike rider is going on a ride. The road contains n + 1 points at different altitudes. The rider starts from point 0 at an altitude of 0.

Given an array of integers gain of length n, where gain[i] represents the net gain in altitude between points i and i + 1 for all (0 <= i < n), return the highest altitude of a point.

Examples

Example 1

• Input: gain = [-5, 1, 5, 0, -7]
• Expected Output: 1
• Justification: The altitude changes are [-5, -4, 1, 1, -6], where 1 is the highest altitude reached.

Example 2

• Input: gain = [4, -3, 2, -1, -2]
• Expected Output: 4
• Justification: The altitude changes are [4, 1, 3, 2, 0], where 4 is the highest altitude reached.

Example 3

• Input: gain = [2, 2, -3, -1, 2, 1, -5]
• Expected Output: 4
• Justification: The altitude changes are [2, 4, 1, 0, 2, 3, -2], where 4 is the highest altitude reached.

Constraints:

• n == gain.length
• 1 <= n <= 100
• -100 <= gain[i] <= 100

Solution

To solve this problem, we'll track the cumulative altitude as we traverse the array of altitude changes. We start with an initial altitude of zero. As we iterate through the array, we continually update the current altitude by adding the current change (which could be positive, negative, or zero) to it.

Simultaneously, we keep track of the highest altitude reached so far. This can be done by comparing the current altitude with the maximum altitude recorded after each update. Once we have gone through all the changes, the recorded maximum altitude is the answer. This approach efficiently calculates the highest altitude with a single pass through the array, ensuring optimal time complexity.

Here is the solution with detailed steps.

1. Initialize Variables:

   • Start by initializing two variables: currentAltitude and maxAltitude.
   • Set both currentAltitude and maxAltitude to 0, as the starting point is considered at sea level (zero altitude).

2. Iterate Through the Array:

   • Loop through each element of the given array of altitude changes.
   • For each element in the array, consider it as a change in altitude (gain or loss).

3. Update Current Altitude:

   • During each iteration, add the current element (altitude change) to currentAltitude.

4. Check and Update Maximum Altitude:

   • After updating currentAltitude, compare it with maxAltitude.
   • If currentAltitude is greater than maxAltitude, update maxAltitude with the value of currentAltitude.
   • This ensures that maxAltitude always holds the highest altitude reached so far.

5. Continue Until the End of the Array:

   • Continue the process of updating currentAltitude and checking/updating maxAltitude until you reach the end of the array.

6. Return the Highest Altitude:

   • After completing the iteration through the entire array, maxAltitude will hold the highest altitude reached during the journey.
   • Return maxAltitude as the final result.

Algorithm Walkthrough