Найдите подпоследовательность, которая при обращении дает максимальный подмассив суммы

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

Примеры:

Input: arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}
Output: [-2 -3 1 5]
Explanation : After selecting subsequence -2 -3 1 5 and reverse it elements, modified array will be {5, 1, 4, -1, -2, -3, -2, -3} and thus the maximum contagious sum   i.e. 5 + 1 + 4 = 10 

Input: arr[] = {2, -6, -12, 7, -13, 9, -14}
Output: [-6 -12 7 9] 
Explanation: After selecting the above subsequence modified array will be {2, 9, 7, -12, -13, -6, -14} and thus  the maximum contagious sum i.e. is 2 + 9 + 7 = 18

Подход: Идея проста: мы должны изменить массив так, чтобы все положительные элементы объединялись, поэтому мы должны найти подпоследовательность, в которой все положительные элементы объединяются, когда мы обращаем подпоследовательность.

• Предположим, что в массиве есть « p » неотрицательных элементов. Разделите массив на две части: первые p элементов и остальные элементы.
• пусть « p ^x » — неотрицательные элементы в первой части массива. поэтому отрицательными элементами в первой части будут:

(size of first part of  array – number of non-negative elements) = p –  p^x

• Также количество неотрицательных элементов во второй части массива равно

(total non-negative elements – non-negative elements in first part of array) =  p – p^x 

• Таким образом, мы должны выбрать отрицательные элементы pp ^x элементов из первой части и pp ^x неотрицательных элементов из второй части массива.

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

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

Связанная тема: Подмассивы, подпоследовательности и подмножества в массиве