Minimum Number of Increments on Subarrays to Form a Target Array

Hard · Greedy · about 20 minutes

Asked at Google, Amazon, Microsoft.

You have an array of zeros as long as target. A single step adds 1 to every element of some contiguous range. What is the fewest steps that turn the zeros into target?