Максимизируйте сумму K пар, состоящих из элементов, равноудаленных от обоих концов массива.

Дан массив arr[] , состоящий из N целых чисел и целого числа K , задача состоит в том, чтобы найти максимальную сумму K пар вида (arr[i], arr[N – i – 1]) , где (0 ≤ i ≤ N – 1) .

Примеры:

Input: arr[] = {2, -4, 3, -1, 2, 5}, K = 2
Output: 9
Explanation: All possibles pair of the form (arr[i], arr[N – i + 1]) are:

1. (2, 5)
2. (-1, 3)
3. (-4, 2)

From the above pairs, the K(= 2) pairs with maximum sum are (2, 5) and (-1, 3). Therefore, maximum sum = 2 + 5 + (-1) + 3 = 9.

Input: arr[] = {2, -4, -2, 4}, K = 2
Output: 0

Наивный подход: самый простой подход к решению задачи — сгенерировать все возможные пары заданной формы из массива и вычислить максимальную сумму K таких пар. После проверки всех пар выведите максимальную сумму, полученную среди всех возможных сумм.

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

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

• Инициализируйте вектор, скажем, pairwiseSum[] , чтобы хранить суммы требуемых пар из массива.
• Сгенерируйте пары (arr[i], arr[N – i + 1]) из заданного массива путем обхода массива. Сохраните их суммы в вектореpairwiseSum[] .
• Отсортируйте вектор попарноSum[] в порядке убывания.
• После выполнения вышеуказанных шагов выведите сумму первых K элементов вектораpairwiseSum[] как результирующую сумму.

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

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