Как максимизировать сумму?

Question

Нам дан отсортированный массив.

Пусть начальное значение pass равно нулю.

Мы можем выполнить следующую операцию любое количество раз:

1. Выберите любое число k одновременно. Добавьте их всех. Добавьте эту сумму к pass

2. Если число, скажем x, выбирается для первый раз из массива, то оно считается только x. Когда он выбран для второй раз , то он считается -x, а в третий раз снова x и т. Д. *

Например, пусть массив будет [-14, 10, 6, -6, -10, -10, -14] и k = 4, и мы сделаем операцию только один раз. Мы выбираем эти 4 числа: {14, 10, 6, -6}. Сложив их, мы получим 24. Тогда pass=pass+24. Следовательно, максимальное значение прохода составляет 24.

Как получить максимальное значение pass?

Answer 1

Мы можем переформулировать проблему следующим образом:

У нас есть список номеров, и мы можем активировать или деактивировать номера.Мы хотим найти максимальную сумму активированных номеров, где на каждом проходе мы можем переключаться ровно k номеров.

Для нечетных k мы могли бы сделать следующее: Активировать максимальное число (если оноположительным) и используйте оставшиеся (k-1) переключатели для переключения любого числа дважды, что фактически оставит номер в его предыдущем состоянии.Следовательно, максимальное значение pass является суммой положительных чисел.

Для четных k это немного отличается, поскольку число активированных чисел всегда четное.Поэтому мы сначала находим все положительные числа.Пусть количество положительных чисел будет p.Если p чётно, то мы хороши, и сумма этих чисел является результатом.Если p нечетно, мы должны проверить два случая: удалить наименьшее положительное число или добавить наибольшее неположительное число.Максимум этих двух случаев является результатом.

Редактировать из комментариев:

Для особого случая, когда k=n, есть только два варианта: либо включить все числа, либо исключить все числа.Если сумма чисел больше 0, это результат.В противном случае результат равен 0.