Problem
Suppose the array can be partitioned in some segments such that in the sorted array no element leave their segment then it is always optimal to do the operations on the segments separately
for example: let A={ 3 ,4, 1, 2, 8 ,9 ,5 ,5 , 9 ,10, 9, 10} then we can partition the array as
A={(3 ,4 ,1 ,2),(8 ,9, 5 ,5),(9),(10,9),(10)} cost=4-1+9-5+9-9+10-9+10-10=8
consider two segments (a…b),(c,…d) and if we have that a<=b<=c<=d the following always hold
(d-a) > = (d-c)+(b-a) thus it is never optimal to merge segments
now the only problem left if to identify the segments, suppose the maximum of ith segment is x and minimum of i+1th segment is y then it is true that x<=y by this fact we can identify the endings of the segment to do this we will maintain two arrays mx which stores the mx[i]=max(A[1]…A[i]) and mn which stores mn[i]=min(A[i]…A[n]) and if an index id is an endpoint of a segment then the following will hold
mx[id]<=mn[id+1] ,and the converse is also true
example:
A___ : 3_4 1 2 8 9 5 5 9 10
mx _ :3 4 4 4 8 9 9 9 9 10
mn_ : 1 1 1 2 5 5 5 5 9 10
seg : (_____) (_____) ()()
when mx[id]<=mn[id+1] seg[id]=‘) and seg [id+1]=’(’
so we have 4 segments here
IMPLEMENTATION