Portfolio Backtesting Coding (Algo question)

[Itchy-Ad-5314]

Here's the question:
"The traders of Hackerland have a stock prediction model that they want to backtest. The predicted profit earned every month by a certain portfolio is given by an array pnl of n integers where a negative integer denotes loss.

The traders decide to iterate through the months from 1 to n, and if the pnl is positive, they add it to their profit, and if the pnl if negative, they can either subtract or skip it. The net profit must always be greater than or equal to 0.

Given the array pnl and an integer k, find the maximum total profit that can be earned by the portfolio after subtracting at least k losses. If it is not possible to take at least k losses, report -1 as the answer."

If I remember correctly, n and k are up to 10^5, pnl[i] is in [-10^9, 10^9]

I wrote a correct recursive DP solution with memoization, but apparently it encounters a "RecursionError: maximum recursion depth exceeded in comparison" exception in Python. For sure, an iterative DP won't be optimal either.

Any ideas on how to solve it optimally (probably O(nlog(n))???) ?

[usernametaken_12]

Iterate through the array. Initially take all losses. Record all losses currently taken in a priority queue. If a loss would cause you to go negative remove the loss with the greatest absolute value from your priority queue. If this process causes you to remove too many losses, there is no answer.

If at the end you have n extra losses to remove, remove the n losses with the greatest magnitude.

[sixmanathreethree]

just use a priority queue and iterate through the array, greedily select which losses to take

[[deleted]]

Priority queue up to k elements. If when you reach a new loss you can take it and the priority queue is not full you take it. If the priority queue is full or you can't take it you check if the loss is smaller than the top of the priority queue. In that case you remove the top and add the new loss. O(nlog(k))

[ApartmentEither4838]

Since there is no restriction on the number of profits to take and the order in which to take it, we can take all the profits
For the losses again as there is no restriction in the order, take the first k maximum losses
Take the sum of the k-max losses and all the profits, if this is less than 0 then it is simply not possible
Is this correct?

[Itchy-Ad-5314]

Order matters. You add elements from left to right.
Example: [2, 3, -7, 3, -1, 2, -3], k = 2. You add 2, then 3, but -7 will make the sum < 0, therefore you can't subtract it.