Найдите максимальную сумму подпоследовательности после перестановки знаков не более чем K элементов в заданном массиве

Опубликовано: 21 Сентября, 2022

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

Примеры:

Input: arr = [6, -10, -1, 0, -4, 2], K = 2
Output: 22
Explanation: Maximum sum can be obtained by flipping -10 and -4 to 10 and 4 respectively

Input: arr = [1, 2, 3], K = 3
Output: 6

Подход : выполните следующие шаги, чтобы решить проблему:

  • Сортировать массив
  • Инициализируйте переменную sum равным 0, чтобы сохранить максимальную сумму подпоследовательности
  • Перебрать массив и преобразовать отрицательный элементы в положительные и уменьшать k до тех пор, пока k > 0
  • Пройдите массив и добавьте только положительные значения для суммирования
  • Вернуть сумму ответа

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


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

РЕКОМЕНДУЕМЫЕ СТАТЬИ