Link of the problem :http://www.spoj.com/problems/TOINCSEQ/
In short: You are given a sequence of non-negative integers a1, a2, …, an. You are allowed to perform some operators on the sequence. Each operator consists of 2 steps: choosing an arbitrary value, then increasing (or decreasing) all elements of the selected value in the current sequence by 1.
For example, the sequence 1 9 9 2 2 will become 1 9 9 3 3 if you decide to increase all elements of value 2.
What is the minimum number of operators does it take to make the given sequence a non-decreasing sequence?
Input
The first line consits of an integer N, the number of elements in the sequence. The second line consists of N elements of the sequence. Output
The mininum number of operators needed to make the sequence non-decreasing. Example
Input: 5
1 9 9 2 2
Output: 7 Constraints
1 ≤ N ≤ 10^5. Each element of the sequence is a non-negative integer not exceeding 10^9. ***************************************************************************
I think we can uses DP but I had no idea then.
Help me please !!!
Remove duplicates from array. Question then becomes this
DP is O(n2). Idea for O(nlogn) is here
Thank for your idea but it may have a few differences when we can increase all elements of the same value instead of one by one :)
REMOVE DUPLICATES IN BEGINNING. Then the problem is same.
what about this test case?
5
5 4 3 2 1
ans = 4
My solution: link
when there exist a value strictly less than the one before it add a segment [ ai , ai - 1 ]
answer is the union of those segments