Минимизируйте затраты на сортировку массива, перемещая элементы со стоимостью в качестве самого значения.

Учитывая массив arr[] из N положительных целых чисел, задача состоит в том, чтобы найти минимальную стоимость сортировки данного массива путем перемещения элемента массива в любую позицию так, чтобы стоимость перемещения этого элемента равнялась значению этого элемента.

Примеры:

Input: arr[] = {7, 1, 2, 3}
Output: 6
Explanation:
Following are the possible set of moves to sort the array with minimum cost:

• Move 1 to the front, arr[] = {1, 7, 2, 3}. cost = 1
• Move 2 to 2nd place, arr[] = {1, 2, 7, 3}. cost = 2
• Move 3 to 3rd place, arr[] = {1, 2, 3, 7}, cost = 3

Therefore, the total cost is (1 + 2 + 3) = 6.

Input: arr[] = {7, 1, 2, 5}
Output: 7

Подход: Данную проблему можно решить с помощью динамического программирования. Идея состоит в том, чтобы зафиксировать элементы массива, образующие самую длинную неубывающую подпоследовательность, имеющую максимальную сумму, и выполнить заданные перемещения ко всем оставшимся элементам массива. Выполните следующие шаги, чтобы решить проблему:

• Найдите самую длинную неубывающую подпоследовательность с максимальной суммой и сохраните ее в переменной, скажем, S .
• После вышеуказанного шага выведите значение ( сумма элементов массива – S) как результирующую возможную минимальную стоимость сортировки данного массива.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² )
Вспомогательное пространство: O(N)