Problem: You are required to sort an array with numbers from 1 to n. You can do a "move", which means choosing one element and moving it to
any place you want (insert to any place, not swap). Prove the minimum number of "moves" to sort the array is
n - k, where
k = the length of the longest increasing subsequence.
Ex: array is
[1, 2, 5, 3, 4, 7, 6]
Longest increasing subsequence is
[1, 2, 3, 4, 6], which is of length
5. Hence, the answer is
7 - 5 = 2 moves. You move numbers
7 to the correct spots.
I'd like a proof / intuition on why this has to be the minimum # of moves.