Destopia's blog

How to solve this problem?
By Destopia, history, 2 years 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

Comments Comments (7)
| Write comment?
»
2 years 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}.}$$$
→ Reply
»
2 years 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.

→ Reply
»
2 years 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

→ Reply