Today we review the increasing subsequence problem similar to the previous two subsequences problems yesterday. Consider a bookshelf with 12 volumes of encyclopedia. Their order has become quite random:
                11, 1, 10,  4, 3, 2, 8, 7, 12, 6, 9, 5
In one move we can take out one volume and insert it anywhere in the row of volumes (shifting some volumes if needed) What is the minimal number of moves necessary to order the volumes from left to right.
The hint provided here is : what is the largest set of volumes that may be left and not moved at all.

To answer the hint, we say that those that form an increasing subsequence in the given sequence are already sorted. Then we can insert all the remaining volumes in their correct positions.
Therefore, the requested number of moves = the length of the sequence - the length of its longest subsequence.
Now to find the longest subsequence, we do the following:
for each element, we find the increasing subsequence upto that element and note its length. Then we take the maximum of such lengths.
For 11 and 1, this length is 1. For 10 this length is 2.  The same holds fror the next three elements. For 8 this is 3 and for 12 this is 4 the maximum. For 6 this is 3. For 9 this is 4 as well. (1,2,6,9)
Generally, for each element x, either:
x can be a single-element increasing sequence or
x can be appended at the end of the longest increasing subsequence ending at some y provided that y precedes x and y < x
Therefore the table looks like this:
Volume       11, 1, 10,  4, 3, 2, 8, 7, 12, 6, 9, 5
Length of     1   1    2   2  2  2  3  3   4   3  4, 3
subsequence
Hence, the smallest number of moves = 12 - 4 = 8.
Note that this is not a single problem of a longest increasing subsequence but a whole table of such problems. The dependencies between increasing subsequence ending at that element makes it easier to calculate their lengths With dynamic programming, the time complexity is O(n^2) where n is the number of volumes. This is better than n times O(nlogn) times complexity using the classical
solution for the longest increasing subsequence.

Heavy Encyclopedia
Let us now modify the problem to say that the encyclopedia volumes are so heavy that they cannot be shifted or taken one position to the other. Instead we want to order the volumes only by swapping the adjacent volumes on the shelf. What is the minimal number of such moves ?
The hint here is that we move the first volume to the first position by swapping with all of the volumes in between the current position and the first. Then we eliminate first and repeat with the second. This will correctly give the minimal number of moves because we are only going to move this volume in one direction and given that there is only one step the total number of moves doesn't change from i-1. Moreover if the volume 1 is not at its intended destination, it will be swapped for subsequent volumes and that will not result in an optimal solution. We therefore use the hint and do successive elimination after each volume makes it to its destination position.
Given this we can print a table of sequences after each volume makes it to its intended positon incrementally.  The total number of moves will come out to be Sum (CurrentPosition(i)-1) for i = 1 to 12 = 31
Without going through the table of sequences, we can total from the given sequence by saying that we add the number of moves needed to position volume x equal the number of such volumes y that y > x and y is to the left of the x in the original problem. Therefore volume 11 will have zero moves.
Here we are using greedy programming when swapping and divide and conquer rule when eliminating.

#codingexercise
Double  GetNthRootProductEachTermRaisedPDividedQoverPTimesQ (Double [] A,Double  p, Double q)
{
If ( A== null) return 0;
Return A.NthRootProductEachTermRaisedPDividedQoverPTimesQ(p, q);
}