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 !!!