Длина самой длинной подпоследовательности, при которой сумма префиксов в каждом элементе остается больше нуля

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

Пример:

Input: arr[] = {-2, -1, 1, 2, -2}, N = 5
Output: 3
Explanation: The sequence can be made of elements at index 2, 3 and 4. The prefix sum at every element stays greater than zero: 1, 3, 1

Input: arr[] = {-2, 3, 3, -7, -5, 1}, N = 6
Output: 12

Подход: Данную задачу можно решить с помощью жадного подхода. Идея состоит в том, чтобы создать очередь с приоритетом минимальной кучи и пройти массив слева направо. Добавьте текущий элемент arr[i] в сумму и minheap, и если сумма станет меньше нуля, удалите самый отрицательный элемент из minheap и вычтите его из суммы . Для решения проблемы можно использовать следующий подход:

• Инициализировать мини-кучу со структурой данных приоритетной очереди
• Инициализировать переменную sum для вычисления суммы префиксов желаемой подпоследовательности
• Повторите массив и в каждом элементе arr[i] и добавьте значение в сумму и минимальную кучу
• Если значение суммы становится меньше нуля, удалите самый отрицательный элемент из минимальной кучи и вычтите это значение из суммы .
• Возвращает размер минимальной кучи как длину самой длинной подпоследовательности

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

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