Программа Javascript для максимальной разницы между группами размера два

Учитывая массив из четного числа элементов, сформируйте группы из 2, используя эти элементы массива, так, чтобы разница между группой с наибольшей суммой и группой с наименьшей суммой была максимальной.
Примечание. Элемент может быть частью только одной группы и должен быть частью как минимум 1 группы.
Примеры:

Input : arr[] = {1, 4, 9, 6}
Output : 10
Groups formed will be (1, 4) and (6, 9), 
the difference between highest sum group
(6, 9) i.e 15 and lowest sum group (1, 4)
i.e 5 is 10.


Input : arr[] = {6, 7, 1, 11}
Output : 11
Groups formed will be (1, 6) and (7, 11), 
the difference between highest sum group
(7, 11) i.e 18 and lowest sum group (1, 6)
i.e 7 is 11.

Простой подход: мы можем решить эту проблему, составив все возможные комбинации и проверив каждый набор различий комбинаций между группой с наибольшей суммой и с наименьшей суммой. Всего будет сформировано n*(n-1)/2 таких групп (nC2).
Сложность времени: O (n ^ 3), потому что для создания групп потребуется O (n ^ 2), а для проверки каждой группы потребуется n итераций, поэтому в целом это занимает O (n ^ 3) времени.
Эффективный подход: мы можем использовать жадный подход. Отсортируйте весь массив, и наш результат будет суммой двух последних элементов минус сумма первых двух элементов.

Выход:

11

Временная сложность: O (n * log n)
Дальнейшая оптимизация:
Вместо сортировки мы можем найти максимум два и минимум два за линейное время и уменьшить временную сложность до O(n).

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

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

Пожалуйста, обратитесь к полной статье о максимальной разнице между группами размера два для получения более подробной информации!