Given an array A[1 .. N], which contains N integers.
I need to sort this array.But the only operation that I can perform on array is :
Reverse all elements in some sub-array, which is a consecutive parts of A which means choose two integers L and R (1 <= L < R <= N), and swap elements A[L] and A[R], A[L+1] and A[R-1], A[L+2] and A[R-2] and so on.
In such operation of L, R, the total cost is R - L + 1. Now i want that array should be sorted by spending minimum cost and also in minimum moves.
Whats the best approach to solve this problem.
Their can be many solution to this problem as this is an optimisation problem.
But what can be a solution near to best possible answer.
EXAMPLE : Let N=6 and array be [2,1,5,4,3,2] Then it can be done in 2 moves
These are : First swap elements in segment [3,6] so the array becomes [2,1,2,3,4,5].Second move is swap elements in segment [1,2] So the final array becomes [1,2,2,3,4,5] Which is sorted array.