Самая длинная подпоследовательность с неотрицательной суммой префиксов в каждой позиции

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

Примеры:

Input: arr[] = {4, -4, 1, -3, 1, -3}
Output: 5
Explanation:
Consider the subsequence as {4, 1, -3, 1, -3}. Now, the prefix sum of the chosen subsequence is {4, 5, 2, 3, 0}. Since, the prefix sum is non-negative at every possible index. Therefore, this subsequence is of maximum length having length 5.

Input: arr[] = {1, 3, 5, 7}
Output: 4

Наивный подход: самый простой подход к решению этой проблемы состоит в том, чтобы сгенерировать все возможные подпоследовательности заданного массива и напечатать длину той подпоследовательности, которая имеет неотрицательную сумму префиксов в каждой позиции и имеет максимальную длину.

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

Эффективный подход. Описанный выше подход также можно оптимизировать с помощью динамического программирования, поскольку он имеет свойство «Перекрывающиеся подзадачи» и свойство «Оптимальная подструктура». Как и в других задачах динамического программирования (DP), повторного вычисления одних и тех же подзадач можно избежать, создав временный массив, в котором хранятся результаты подзадач. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте матрицу, скажем, dp[][] , где dp[i][j] хранит максимально возможную сумму, если есть j допустимых элементов до позиции i и инициализация массива dp[][] с -1 .
• Переберите диапазон [0, N – 1], используя переменную i , и обновите dp[i][0] как 0 .
• Если значение arr[0] не меньше 0 , тогда обновите dp[0][1] как arr[0] . В противном случае обновите его как -1 .
• Перебрать диапазон [1, N – 1], используя переменную i :
  • Перебрать диапазон [1, i + 1], используя переменную j :
    • Если текущий элемент исключен , т.е. если dp[i – 1][j] не равно -1 , то обновить dp[i][j] как максимальное из dp[i][j] и dp[i – 1] [ж] .
    • Если текущий элемент включен , т. е. если dp[i – 1][j – 1] и dp[i – 1][j – 1] + arr[i] больше, чем равно 0 , тогда обновите значение dp[ i][j] как максимум dp[i][j] и dp[i – 1][j – 1] + arr[i] .
• Инициализируйте переменную, скажем , как 0 , чтобы сохранить самую длинную подпоследовательность с неотрицательной суммой префиксов в каждой позиции.
• Выполните итерацию в диапазоне [0, N], используя переменную j , и если dp[N – 1][j] больше, чем равно 0 , затем обновите значение ans как j .
• После выполнения вышеуказанных шагов выведите в качестве результата значение ans .

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

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