Find the Highest Altitude — LeetCode 1732 Python Solution

The problem

There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes.

Example

Input

gain = [-5,1,5,0,-7]

Output

1

Explanation

The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.

Python solution

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        return max(accumulate(gain, initial=0))

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 1732. Find the Highest Altitude is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems