Максимальная сумма массива после удаления положительного или отрицательного подмассива

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

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

Примеры:

Input: arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}
Output: 4
Explanation: Maximum array sum can be obtained by removing subarray arr[0, 1] since arr[0, 1] has same type of elements i.e., negative. Thus, the required sum is 4.

Input: arr[] = {2, -10, 4, 2, -8, -7}
Output: -2
Explanation: Maximum array sum can be obtained by removing subarray arr[4, 5] since arr[4, 5] has same type of elements i.e., negative. Thus, the required sum is -2. 

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

  • Пройдите массив, arr[] и сохраните общая сумма массива в переменной, скажем, sum .
  • Сохраните максимальную непрерывную отрицательную сумму в переменной, скажем, max_neg .
  • Если в массиве нет отрицательных элементов, то обновить max_neg до наименьший элемент массива.
  • Обновите значение суммы до (sum – max_neg) .
  • В качестве результата выведите значение суммы .

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

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

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