Given an array A of N elements we can perform the following kind of updates on it:

Pick an i and add 1 to all elements in range [i,N]

What is the minimum number of updates such that there is no element in A equal to 0. That is, the minimum number of updates such that for each i A[i] != 0

CodePudding user response：

Observation 1: order in which we apply the increments does not change the result. With this observation there exists the optimal increments where all increments are applied to increasing indices.

Observation 2: if we have a correct solution and at the moment of application of increment to range [i, N] it is true that A[i] != 0 the solution where this increment is replaced with increment [i 1, N] is also correct.

With these two observations in mind we know that there is an optimal solution where increments are applied left to right and every increment is applied at index i such that A[i] == 0. That makes the following algorithm correct (written in pseudocode):

increments=0
for i=1 to N
  if A[i]   increments == 0
    increments  = 1

Here to add 1 to the suffix as i am looping with increasing indices i just store in the variable how many increments would affect current index, and it so happens that after the loop finishes it also contains the answer.