Destopia's blog

By Destopia, history, 7 weeks ago, In English

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
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 weeks ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

1) Construct the difference array with d[0] = a[0] and d[i] = a[i] — a[i — 1], for i > 0

2) ans = max( sum_of_positive_elements, abs(sum_of_negative_elements) )

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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