744. The Highest Point of the Climb

A walk starts at altitude 0. The ith step changes the altitude by a[i], which may be negative. Print the HIGHEST altitude reached at any point, including the starting point.

-5 1 5 0 -7 -> 1 -4 -3 -2 -1 4 3 2 -> 0 1 2 3 -> 6 5 -10 5 -> 5

## The altitudes are the prefix sums

After i steps the altitude is a[0] + ... + a[i-1], which is the ith prefix sum. So the answer is the largest prefix sum.

No array is needed. Carry one running total and one running maximum:

run = 0; best = 0 for v in a: run += v best = max(best, run)

## The starting point counts

best begins at 0, not at the first altitude and not at negative infinity, because the walk starts at 0 and never being above it is a legitimate answer.

On -4 -3 -2 -1 4 3 2 every altitude along the way is negative, so the answer is 0, the altitude before the first step. Seeding best with a[0] gives -4, and seeding it with the first prefix gives the same. That case is in the samples for exactly this reason.

## What NOT to do

Building the full array of prefix sums and taking its maximum is correct and uses O(n) extra space for nothing. The running form is the same work in constant space.

## Relationship with problem 745

745 asks the mirror question: given the same steps, what is the smallest starting altitude that keeps the walk at or above 1 throughout. That answer comes from the running MINIMUM.

Same sweep, opposite extreme, and the pair is worth solving together.

## Overflow

10^5 steps of 10^4 reach 10^9, which fits in a signed 32 bit integer but only just. 64 bits costs nothing.

## What most people try first

Building the whole array of prefix sums and taking its maximum. That is correct and spends O(n) memory to hold values that are each read once. The running form below is the same work in constant space.

## Cost

Time O(n). Space O(1).

Constraints - `1 ≤ n ≤ 100000` - `-10^4 ≤ each value ≤ 10^4`