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

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

• Если arr[i] < arr[i+1] , увеличить счет на 1 .
• В противном случае держите счет на том же уровне.

Примеры:

Input: N = 5, arr[] = {5, 7, 9, 5, 8} 
Output: {5, 7, 8, 9, 5}
Explanation: After rearranging the array, absolute difference of first and last element = abs(5 – 5) = 0, which is the minimum possible.
Maximum score that can be achieved : 

• arr[0] < arr[1], score = 1
• arr[1] < arr[2], score = 2
• arr[2] > arr[3], score = 3
• arr[3] > arr[4], score = 3

Input: N = 4, arr[] = {6, 4, 1, 3}
Output: {3, 6, 1, 4}

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

1. Отсортируйте массив и найдите наименьшую абсолютную разницу между каждой парой соседних элементов и сохраните его индекс, скажем, ind .
2. Теперь работайте только с элементами, оставшимися помимо этих двух элементов по индексам ( ind – 1 и ind ). Эти два элемента будут первым и последним элементами требуемого массива.
3. Решите проблему, сохранив оставшиеся элементы двумя способами:
   • Сначала сохраните элементы в массиве res, которые больше , чем элемент с индексом (ind — 1) .
   • Затем сохраните в массиве res элементы, которые меньше или равны элементу с индексом (ind).
4. В конце нажмите последний элемент, т. е. элемент с индексом (ind), и верните вектор разрешения.

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

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