Approach: Running max of prefix

def largestAltitude(gain):
    h = best = 0
    for g in gain:
        h += g; best = max(best, h)
    return best

Complexity: O(n) time, O(1) space.

Full Solution — all languages

class Solution:
    def largestAltitude(self, nums):
        h = best = 0
        for g in nums:
            h += g
            best = max(best, h)
        return best

import java.util.*;
class Solution {
    public int largestAltitude(int[] nums) {
        int h = 0, best = 0;
        for (int g : nums) {
            h += g;
            best = Math.max(best, h);
        }
        return best;
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: int largestAltitude(vector<int>& nums) {
        int h = 0, best = 0;
        for (int g : nums) {
            h += g;
            best = max(best, h);
        }
        return best;
    }
};

/**
 * @param {number[]} nums
 * @return {number}
 */ var largestAltitude = function(nums) {
    let h = 0, best = 0;
    for (const g of nums) {
        h += g;
        if (h > best) best = h;
    }
    return best;
};

Find the Highest Altitude

Example 1

Example 2

Constraints