645. Handing Out Sweets Fairly
Children stand in a row, each with a rating. Every child gets at least one sweet, and a child with a HIGHER rating than an immediate neighbour must get strictly more sweets than that neighbour.
Print the fewest sweets that satisfy both rules.
1 0 2 -> 5 2, 1, 2
1 2 2 -> 4 1, 2, 1
1 2 3 4 -> 10
## Two rules pulling in opposite directions
Each child is constrained by the neighbour on its LEFT and by the one on its RIGHT. Trying to satisfy both in a single pass fails, because fixing a child for its left neighbour can break the rule for its right neighbour, and repairing that can break an earlier one.
Repeatedly sweeping until nothing changes is correct and can take O(n) sweeps, so O(n^2).
## One pass for each direction
Give everyone 1, then:
left to right: if rating[i] > rating[i-1]: c[i] = c[i-1] + 1
right to left: if rating[i] > rating[i+1]: c[i] = max(c[i], c[i+1] + 1)
After the first pass every LEFT constraint holds. The second pass fixes the right constraints,
and the max is what stops it from breaking the left ones: it only ever RAISES a value, and
raising a child never violates a rule that said it must be larger than something.
That last sentence is the whole correctness argument, and the max is where it lives.
Assigning c[i] = c[i+1] + 1 outright instead can lower a value and undo the first pass.
## Why the answer is the minimum
Every value ends as small as some chain of constraints forces it to be. Formally, each c[i]
equals 1 plus the length of the longest strictly decreasing run starting at i in either
direction, and any valid assignment must be at least that.
So the two passes do not merely find A valid answer; they find the smallest one.
## The input to trace
1 3 2 2 1 answers 7, as 1 3 1 2 1. The middle pair of equal ratings is the interesting
part: equal neighbours impose NO constraint in either direction, so the second 2 is free to
restart at a low value.
Reading the rule as "different ratings need different sweets" gives a larger answer and is a misreading; only a HIGHER rating forces more.
## Overflow
With 200000 strictly increasing ratings, the last child receives 200000 sweets and the total is
about 2 * 10^10. The TOTAL needs 64 bits even though each individual count fits in 32.
## Cost
Time O(n) in two passes. Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ each rating ≤ 10^9`
Input
The first line contains an integer n.
The second line contains n integers, the ratings.
Output
Print one integer, the fewest sweets needed.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.