849. Fewest Passes to Build the Target Profile

A row of n columns starts at height 0 everywhere. In one PASS you may choose any contiguous range of columns and add exactly 1 to each of them.

Given the target heights t[0] ... t[n-1], print the smallest number of passes that reaches them exactly.

1 2 3 2 -> 3 3 1 1 2 1 -> 4 0 1 0 1 0 1 0 1 -> 4

For the first row: one pass over all four columns, one over the last three, one over the third alone. Three passes, and no two passes can do it.

## The stack view, which is where the answer comes from

Sweep left to right with a stack of the heights of the passes currently OPEN, that is, the passes whose range has started and not yet ended. The stack is increasing from the bottom up, since a pass that started later can only be nested inside the ones already open.

At column i, the open passes must total exactly t[i], so:

* if t[i] > t[i-1], you must OPEN t[i] - t[i-1] new passes here * if t[i] < t[i-1], you must CLOSE t[i-1] - t[i] of them, popping from the top * if equal, nothing changes

Every pass is opened exactly once, so the answer is the total number of opens:

answer = t[0] + sum over i >= 1 of max(0, t[i] - t[i-1])

which is the same as the formula with t[-1] treated as 0.

## Why no schedule can do better, and why this one works

Lower bound: whenever t[i] > t[i-1], at least t[i] - t[i-1] passes must begin exactly at column i, because a pass covering column i and column i-1 contributes to both, so the excess at i can only come from passes that start there. Adding those forced starts across all i gives the formula as a lower bound.

Upper bound: the sweep above actually builds a schedule with that many passes, closing them greedily on the way down. So the bound is achieved and the answer is exactly the sum.

## Why the stack does not have to exist in the code

Once you see that every open is forced and every close is free, the stack collapses into a single running comparison with the previous column. Keeping the stack is how you SEE the answer; keeping one variable is how you write it. Both are O(n) but only one of them allocates.

That collapse is worth noticing, because a lot of monotonic stack problems have one.

## The edges

The first column has no predecessor, and treating t[-1] as anything other than 0 is the usual off-by-one: a row of 5 alone needs 5 passes, not 0.

Zero targets are allowed and must simply add nothing. The total reaches n times 10^9, so it needs 64 bits.

## Related problems

Problem 858 also collapses a repeated sweep into one stack pass, but its answer genuinely needs the stack because the value carried on it is not a simple difference.

## Cost

Time O(n). Space O(1) beyond the input.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ t[i] ≤ 10^9` - the answer can reach `2 * 10^14`, so it needs 64 bits