### Destopia's blog

By Destopia, history, 7 weeks ago, Given an array of non-positive integers of length $n$ $(1 \leq n \leq 10^5)$ i.e. $a_i \leq 0$. $(-10^9 \leq a_i \leq 0)$ We want to make all elements equal to $0$. We can do the following operation any number of times (possibly zero).

Choose any subarray and increase all its elements by $1$.

What is the minimum number of operations to make all elements equal to $0$?

Input

7

0 -1 -1 -1 0 -2 -1


Output

3 Comments (8)
 » 7 weeks ago, # | ← Rev. 7 →   It would be ${\Large\frac{abs(a_1) + abs(a_n) + \sum_{i=2}^{n} abs(a_i - a_{i-1})}{2}.}$
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   n = 3a = [-2, -10, -2]ans = 10 not 18
•  » » » Yeah true. I updated my formula.Similar problem : Air Cownditioning
•  » » Proof?
•  » » » I think this might help.
 » Traverse from left to right, break array into segments on getting A[i] = 0,solve each segment individually and add them to get final ans. Each segment will be solved as move to min element index in the segment,assign L and R variable as this index,then just increase L to R contigous subarray value to min(A[L-1],A[R+1]) in 1 step and accrodingly change L and R, increasing subarray length.
 » 1) Construct the difference array with d = a and d[i] = a[i] — a[i — 1], for i > 02) ans = max( sum_of_positive_elements, abs(sum_of_negative_elements) )
 » We can show that answer is equal to $\frac{|a_1| + |a_n| + |a_2 - a_1| + |a_3 - a_2| + \dots + |a_n - a_{n - 1}|}{2}$. Try now solve these two problems: USACO, CodeForces