Potions

tags: Running Maximum, Minimum, Subsequences.

Intution

• once taken into account.
• if sum gets negative.
• pop out from priority queue
• because what we desire is the subsequence not the subarray.
• therefore order isn’t the issue here.
• yes with priorityQueue/multiset at the hand.
• i can go back in time and choose to have different thing than once i had.
• because I had them stored.
• similar questions: Maximum Performance of a team, Maximum Subsequence score, Minimum cost to hire K workers, IPO

implementation

```cpp void solve() { int n; cin >> n; priority_queue pq; ll sum = 0; for (int i = 0; i < n; i++) { int num; cin >> num; pq.push(-num); sum += num; while (sum < 0) { sum += pq.top(); pq.pop(); } } cout << pq.size() << '\n'; } ``` </details>