724. Building a Target From Range Increments
Start from an array of n zeros. One move adds 1 to every position of a contiguous range of
your choosing. Print the fewest moves that turn it into the given target array.
1 2 3 2 1 -> 3
3 1 5 4 2 -> 7
0 3 0 3 -> 6
## Read the differences, do not simulate
Every move raises a contiguous range by 1. Look at what that does to the STEPS between
neighbouring positions: a move starting at i raises the step at i by exactly 1, and a move
ending at j lowers the step at j + 1 by exactly 1. Nothing else changes.
So the number of moves STARTING at position i is exactly the rise in the step there, and the
total is the sum of all the rises:
answer = a[1] + sum over i > 1 of max(0, a[i] - a[i-1])
Problem 721 builds an array from its differences. This reads an array's differences back to recover what built it, which is the same identity used from the other side.
## Why only the rises count
A move must start somewhere. If a[i] > a[i-1] then at least a[i] - a[i-1] moves have to
begin at i, because no move covering i-1 can leave i higher than it. If a[i] <= a[i-1]
then no move needs to start at i at all: every move that is still needed can be extended from
the left.
And that many moves is enough, because a move started at i can be continued rightwards for
free until the target drops.
So the bound is tight from both sides, which is what makes this exact rather than merely a lower bound.
## The first position is not a special case in disguise
a[1] is the rise from an implicit zero to the left, so writing the array as if
a[0] = 0 makes the formula a single loop with no leading term. That framing is worth
preferring because it removes the place where an off-by-one lives.
## Boundaries
An all-zero target answers 0. A non increasing target answers a[1], since nothing after it
ever forces a new move, and 4 3 2 1 answering 4 is the check for that.
## Overflow
Rises telescope, so a maximal run of consecutive rising indices contributes at most 10^9 in
total no matter how long it is, and two such runs must be separated by at least one non rising
index. With n = 2 * 10^5 that allows at most 10^5 separated runs, so the answer caps at
10^5 * 10^9 = 10^14. The alternating target 10^9 0 10^9 0 ... hits that figure exactly, so
the total needs 64 bits.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ each target value ≤ 10^9`
Input
The first line contains an integer n.
The second line contains n non negative integers, the target.
Output
Print one integer, the fewest moves.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.