Problem
Given an integer array gain, wheregain[i] represents the net gain in altitude between points i and i + 1, the journey starts at an altitude of 0.
Return the highest altitude reached during the journey.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
gain = [-5,1,5,0,-7]Output
1Example 2
Input
gain = [-4,-3,-2,-1,4,3,2]Output
0Solution
This solution uses the Prefix Sum technique. We start with the current altitude as0 and add each gain value to calculate the altitude at the next point.
After calculating each altitude, we update the maximum altitude reached so far. Since the altitude at each point depends on all previous gains, this running total represents a prefix sum.
class Solution {
public int largestAltitude(int[] gain) {
int altitude = 0;
int maxAltitude = 0;
for (int i = 0; i < gain.length; i++) {
altitude += gain[i];
maxAltitude = Math.max(maxAltitude, altitude);
}
return maxAltitude;
}
}Complexity
Each element is processed exactly once, so the time complexity isO(n), where n is the length of the array.
The solution uses only a few variables to maintain the current and maximum altitude, so the extra space complexity is
O(1).