Максимально возможная разница между двумя подмассивами после удаления N элементов из массива

Дан массив arr[] размера 3*N . Задача состоит в том, чтобы удалить N элементов и разделить весь массив на две равные части так, чтобы разность суммы левого и правого подмассивов была максимальной.

Примеры:

Input: arr[] = [5, 4, 4, 2, 3, 3]
Output: 4
Explanation:  The ‘2’ elements to be removed are [4, 3]. 
and when you divide the array into two equal parts after the removal
left subarray= [5, 4], right subarray= [2, 3]. 
The Sum difference between them is (9-5) = 4

Input: arr[] = [4, 5, 6, 1, 2, 8, 7, 9, 3]
Output: 9

Подход:

Split the array into two subarrays at some point i (N <= i <= 2 * N). We remove i – N smallest elements from the first subarray, and (2 * N – i) largest elements from the second subarray. That way, for a given split, we get the largest possible sum_first, and smallest possible sum_second.

Using Max and Min heap to keep track of the smallest and largest elements, respectively. And update the difference.

Выполните следующие шаги для реализации идеи:

• Инициализируйте переменную final_diff для хранения максимальной разницы между левым и правым подмассивами после удаления N элементов.
• Запустите цикл for от N до 2*N и arr[] на две половины слева и справа.
  • Удалить i – N наименьших элементов из левого массива и 2*N — i самых больших элементов из правого массива с использованием минимальной и максимальной кучи .
  • Вычислить сумму N самых больших значений в левом массиве и N наименьших значений в правом массиве, найдите разницу между ними и сохраните ее в переменной Curr_diff .
  • Максимизируйте значение final_diff с помощью curr_diff .
• Вернуть значение final_diff.

Ниже приведена реализация

Выход:
Максимальная разница между S1 и S2 составляет 13

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