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
It would be
n = 3
a = [-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.
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