Максимизируйте сумму каждого элемента, возведенного в степень его частоты в подмассиве размером K

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

Примеры:

Input: arr[] = { 2, 1, 2, 3, 3 }, N = 5, K = 3
Output: 11
Explanation: Required subarray of size 3 = {2, 3, 3}. The sum is 2¹ + 3² = 11, which is the maximum sum possible.

Input: arr[] = { 4, 9, 6, 5}, N = 4, K = 3
Output: 20
Explanation: The two subarrays of size 3 are {4, 9, 6} and {9, 6, 5}. The subarray {9, 6, 5} has the sum = 20.

Наивный подход: самый простой подход — сгенерировать все подмассивы. Затем для каждого подмассива посчитайте частоту элементов и сгенерируйте сумму. Теперь проверьте суммы, чтобы найти максимальную.

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

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

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

Наиболее эффективный подход: эта идея также основана на технике скользящего окна. Но при таком подходе избегается подсчет частоты каждого элемента для каждого окна. Для реализации идеи выполните следующие шаги:

• Поддерживайте окно размера K , которое обозначает подмассив.
• Когда окно смещается на одну позицию вправо, вычтите вклад элемента, расположенного непосредственно слева от окна, и самого правого элемента окна.
• Теперь отрегулируйте частоту , уменьшив частоту элемента, расположенного непосредственно слева от окна, и увеличив частоту самого правого элемента окна.
• Добавьте обратно вклады в соответствии с новыми частотами элементов, непосредственно слева от окна, и самого правого элемента окна.

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

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