Максимальная сумма двух непересекающихся подмассивов любой длины

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

Дан массив A , состоящий из N целых чисел, задача состоит в том, чтобы найти максимальную сумму двух непересекающихся подмассивов любой длины массива.

Примечание. Вы также можете выбрать пустые подмассивы.

Примеры:

Input: N = 3, A[] = {-4, -5, -2}
Output: 0
Explanation: Two empty subarrays are optimal with maximum sum = 0.

Input:  N = 5, A[] = {5, -2, 3, -6, 5}
Output: 11
Explanation: Optimal subarrays are {5, -2, 3} and {5} with maximum sum = 11.

Подход: Чтобы решить проблему, следуйте следующей идее:

This problem can be thought of as the maximum sum contiguous subarray (Kadane’s Algorithm) from both left and right directions. 
By applying this algorithm, we are ensuring a maximum contiguous sum up to an index that can be stored in two vectors from front and back for finding maximum non-intersecting sum.

Выполните указанные шаги, чтобы решить проблему:

  • Инициализируйте два вектора frontKadane и backKadane с помощью 0 .
  • Пройдите массив A и реализуйте алгоритм Kadane слева направо и сохраните максимальную сумму подмассива в frontKadane[i] .
  • Обход массива A и реализация алгоритма Кадане справа налево и сохранить максимальную сумму подмассива в backKadane[i] .
  • Перейдите от 0 к N и вычислите максимальное значение (frontKadane[i] + backKadane[i]) и сохраните результат в переменной.
  • Возвращаться в результат как окончательный ответ.

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

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

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