Максимизировать конкретную сумму подмассива, переставив элементы массива?

Question

Как максимизировать конкретную сумму подмассива, переставив элементы массива?

Рассмотрим массив следующим образом:

[5,1,4,6,7]

Когда мы выбираем индексы [0,2], чтобы получить сумму подмассива в этом диапазоне, например [5,1,4], мы получаем сумму как 10, но мы можем максимизировать эту сумму, если мы переставим массив as:

[5,7,6,1,4]

Теперь мы максимизировали сумму подмассива для индексов [0,2] как 18.

У нас может быть много запросов для индексов подмассива, для которых мы должны максимизировать сумму.

Как мне поступить? Есть намеки?

Answer 1

Очевидный факт - ваш диапазон должен содержать только самые большие элементы массива.

Следовательно, решение: отсортировать массив, вычислить сумму всех префиксов отсортированного массива. Теперь, если вам нужно максимизировать диапазон длины 3, ответом является сумма первых 3 чисел (уже вычисленных в предварительной обработке).

В этом решении используется O (n log n) при предварительной обработке и O (1) ответить на каждый запрос.