Here is the thing, I am solving an problem, and I think, say, I am pretty sure that I have the correct algorithm but I haven't been able to prove it because of my lack of practice prooving greedy algorithms.
The problem says: I need to sort an array of $n$ numbers, but the only operation I am able to do is to move an element from position $i$ to $j$, and if $i<j$ then every elements in the interval $[i+1, j]$ (inclusive) are moved one position backwards. On the other hand if $i>j$ then every element in the interval $[j, i-1]$ increase their position by one. That operation has a cost of $i+j$ for doing it. So I need to sort the array using the lowest cost possible using a series of only that kind of operations.
Assume that I need to sort the array in decreasing order.
After a lot of thinking, I came up with the idea of finding the (first) longest increasing subsequence from right to left. If I have that sequence, we are to assume that those elements in that sequence are already sorted. So, I wouldn't need to use them (i.e selecting them (from $i$) to move them (to $j$)), cause they are already sorted. That way, the cost of moving them would never be calculated into the final cost of making every operations. And also I will be doing fewer operations and then guaranteeing that the ones I am doing has the lowest cost.
The cost will be easily calculated because the subsequence was created using a sort of Tuple element, with the value and the actual position in the array, so I'll use the value of the position to calculate cost.
After having that subsequence in hand, I am to insert the remaining elements in that sequence (the first longest increasing subsequence from right to left). After that I insert the remaining elements in a Queue to easily Dequeue them in the order of their position (from lowest to highest). That way, we guarantee that the cost of moving them will be minimum. After inserting we update the position of the elements in the sequence (in the Tuple) in the Queue and in the sequence (say I am using a List of Tuple for the sequence).
That algorithm is working, and have thrown a correct answer for several cases I tested against a brute force algorithm version.
Now I need to proove it works, but I have no clue how. It can easily be seen I am using a greedy aproach to insert the elements, but I how does it guarantee what I am looking for!
Hope anyone can point me into the right direction of that proof! Thanks in advance
EDIT: I have done some progress here, and I am in a point where I have proven that the optimum must have selected a decreasing subsequence to avoid those items of being moved, but I need to prove that this is the maximum decreasing subsequence. In order to do that I am trying to prove that the cost of moving $X$ elements is less than the cost of moving $Y$ elements with $X<Y$. I haven't been able to prove it, but I can't come up with an example that prove me wrong.
Do you think this happens? How could I prove it?
Thanks
EDIT: This is the problem itself SPOJ Problem RSORTING - RANKLIST SORTING I have a solution but I need to prove its correctness
