Каким образом можно разделить массив чисел так, чтобы сумма разницы между наибольшим и наименьшим числами была наибольшей?

Для решения первой части вопроса, можно использовать следующий подход:

1. Отсортировать массив чисел по возрастанию.
2. Создать два новых массива: один содержащий все четные элементы и другой содержащий все нечетные элементы исходного массива.
3. Разделить каждый из новых массивов на две равные группы (если возможно), чтобы получить две группы с наибольшей суммарной разницей между максимальным и минимальным числами.

Для второй части вопроса, можно использовать следующий алгоритм:

1. Подсчитать разницу между максимальным и минимальным числами в каждой возможной группе длиной от l до r.
2. Выбрать группу с максимальной суммарной разницей.

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

Пример жадного алгоритма:
1. Отсортировать массив чисел по возрастанию.
2. Создать пустую группу.
3. Переместить каждое число из отсортированного массива в группу, учитывая условия длины каждой группы от l до r.
4. Посчитать суммарную разницу между максимальным и минимальным числами в каждой группе.
5. Выбрать группу с максимальной суммарной разницей.

Ага, ДП тут отлично входит. F(n) - ответ на задачу для префикса длины n. Там перебираете длину последней группы x и берете в качесвте ответа max(a[n-x]..a[n-1]) - min(a[n-x]..a[n-1]) + F(n-x). По всем l<=x<=r выбераете максимум. Если n < l, то ответ - минус бесконечность. 
 
 Это будет решение за O(n^2). Что-нибудь за O(n log n) я так сходу придумать не могу.