To solve the problem, calculate the altitude at each point by starting from altitude 0 and adding up the values from the 'gain' array. This involves iterating through the array and keeping track of the current altitude. At each step, update and compare against the maximum altitude to find the highest point reached during the entire trip.
Time Complexity: O(n), where n is the length of the gain array, as we iterate through the gain array once.
Space Complexity: O(1), as no extra space proportional to input size is used.
1public class HighestAltitude {
2 public static int highestAltitude(int[] gain) {
3 int maxAltitude = 0;
4 int currentAltitude = 0;
5 for (int g : gain) {
6 currentAltitude += g;
7 if (currentAltitude > maxAltitude) {
8 maxAltitude = currentAltitude;
9 }
10 }
11 return maxAltitude;
12 }
13
14 public static void main(String[] args) {
15 int[] gain = {-5, 1, 5, 0, -7};
16 System.out.println(highestAltitude(gain));
17 }
18}In this Java solution, we iterate through the gain array, updating the altitude and checking if it is the highest we've encountered at each step. We compare with the current max and overwrite it if the current altitude exceeds the current max.