4081. Maximum Transactions Without Negative Balance

Medium
Array
Greedy
Heap (Priority Queue)

Description

Hints

Hint 1
Scan the list left to right, keeping a running <code>balance</code> and a container <code>accepted</code> that tracks the sizes of negative transactions you have taken.
Hint 2
Always take nonnegative transactions; they increase <code>balance</code> and the total count.
Hint 3
If a negative <code>t</code> can be paid (<code>balance + t >= 0</code>), accept it and record its absolute value in <code>accepted</code>.
Hint 4
If a negative would make the balance go below zero, but you previously accepted a larger negative, replace that larger one with the current smaller one (restore balance, swap in the smaller): this trade increases the number of transactions you can keep.

Statistics

Acceptance
50.2%
Submissions
984
Accepted
494