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.
1#include <vector>
2#include <iostream>
3
4int highestAltitude(std::vector<int>& gain) {
5 int max_altitude = 0;
6 int current_altitude = 0;
7 for (int g : gain) {
8 current_altitude += g;
9 max_altitude = std::max(max_altitude, current_altitude);
10 }
11 return max_altitude;
12}
13
14int main() {
15 std::vector<int> gain = {-5, 1, 5, 0, -7};
16 std::cout << highestAltitude(gain);
17 return 0;
18}In C++, a vector is used to store gains. The highest altitude is tracked as gains are accumulated one by one. The current altitude updates with each gain and the max altitude is updated if the current is greater than the previous max.