SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem is to find the highest altitude reached after performing a series of gains and losses starting from an initial altitude of zero. Each element in the input array gain represents a change in altitude. The goal is to compute the maximum altitude attained after applying all the changes.

Intuition

To solve this problem, you can iteratively compute the altitude after each change in the gain array, starting from an altitude of zero. As you compute each new altitude, you track the maximum altitude reached.

Approach

1. Initialization: Start with an initial altitude of 0. Keep track of the maximum altitude as you iterate through the gain array.

2. Iteration: For each value in the gain array, update the current altitude by adding the gain to the previous altitude.

3. Tracking Maximum: After updating the altitude, compare it with the current maximum altitude and update the maximum if the new altitude is higher.

4. Return Result: Once all gains have been processed, the maximum altitude recorded will be the result.

Complexity

Time Complexity:

O(n), where n is the length of the gain array. This is because we only need to iterate through the array once.

Space Complexity:

O(1), as we only use a few variables to store the current altitude and the maximum altitude, regardless of the input size.

Code

C++

class Solution {
public:
    int largestAltitude(std::vector<int>& gain) {
        int sum = 0;
        int maxAlt = 0;
        
        for (int i = 0; i < gain.size(); i++) {
            sum += gain[i];
            maxAlt = std::max(maxAlt, sum);
        }

        return maxAlt;
    }
};

Python

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        sum = 0
        max_alt = 0
        
        for g in gain:
            sum += g
            max_alt = max(max_alt, sum)
        
        return max_alt

Java

class Solution {
    public int largestAltitude(int[] gain) {
        int sum = 0;
        int maxAlt = 0;

        for (int i = 0; i < gain.length; i++) {
            sum += gain[i];
            maxAlt = Math.max(maxAlt, sum);
        }

        return maxAlt;
    }
}

JavaScript

var largestAltitude = function (gain) {
    let sum = 0;
    let alt = [];
    let max;
    for (let i = 0; i <= gain.length; i++) {
        alt.push(sum);
        sum = sum + gain[i];
    }
    max = alt[0];
    for (let j = 0; j < alt.length; j++) {
        if (max < alt[j]) {
            max = alt[j];
        }
    }
    return max;
}