Блог пользователя tfgs

Автор tfgs, история, 12 месяцев назад, По-английски

Hello, from this problem I know that the minimum number of relocations to sort the array is N-(length of longest non-dec subsequence). Please, can you help me prove this result?

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

proof by ac:)

»
12 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

The principle behind this is pretty similar to insertion sort's: first consider a sorted subsequence of the array. Then, for every element not in this subsequence, relocate them into their correct position in the array. Therefore, the minimum number of relocations one has to do is equal to the number of out-of-place elements.

For instance, take the array 3, 1, 5, 2, 4 for example, take 3, 5 to be the sorted subsequence (this isn't the optimal solution — for demonstrational purposes only!)

3 1 5 2 4 → 1 3 5 2 4 → 1 2 3 5 4 → 1 2 3 4 5

This would take 3 steps: N — length of sorted subsequence. Bolded elements denote sorted elements. Note that the initial positions of the unsorted elements don't matter — they will be relocated anyways.

Naturally, since we want to minimise the number of relocations, we would want to take the longest nondecreasing subsequence as the initial sorted subsequence. Therefore, the answer to this problem is indeed N minus the length of the longest non-dec subsequence.