leetcode - 1732. Find the Highest Altitude

There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.

You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i and i + 1 for all (0 <= i < n). Return the highest altitude of a point.

Example 1:

Input: gain = [-5,1,5,0,-7]
Output: 1
Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.

Example 2:

Input: gain = [-4,-3,-2,-1,4,3,2]
Output: 0
Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.

In this problem, we are tasked with finding the highest altitude a biker reaches during a road trip, given an array `gain` representing the net altitude change between consecutive points. The biker starts at an altitude of 0 and proceeds through several points, with the altitude at each point determined by adding the respective value from the `gain` array. To solve the problem efficiently, we can keep track of the current altitude as we traverse the `gain` array and update the highest altitude reached so far.

The approach begins by initializing the biker's starting altitude to 0. As we process each element in the `gain` array, we accumulate the altitude at each point. After updating the altitude at each step, we check whether this new altitude is higher than any previously recorded altitude and update the maximum altitude accordingly. This eliminates the need for sorting the altitudes or storing them in an additional array.

The algorithm runs in linear time, O(n), where `n` is the length of the `gain` array, because it only involves a single traversal of the array. The space complexity is O(1) as we only use a fixed amount of space for tracking the current and maximum altitude. This makes the solution both time and space efficient, ensuring that we can handle even large arrays of altitude changes effectively.

CODE:

class Solution {
public:
    int largestAltitude(vector<int>& arr) {
        int n=arr.size();
        int k=n+1;
        int nums[k];
        int max;
        nums[0]=0;
        nums[1]=arr[0];
        int i;
        for(i=2;i<k;i++){
            nums[i]=arr[i-1]+arr[i-2];
            arr[i-1]=nums[i];
        }
        sort(nums,nums+k);
        max=nums[n];
        return max;
    }
};