Longest subsequence with a running sum never below zero

Given an array of n integers ,find the maximum length of a subsequence such that sum of elements is never less than zero at any point in the subsequence moving from left to right .

Examples :

Input :
Size of array  :  n = 6
Array elements :  arr[n] = {4  , -4 , 1 , -3 , 1 , -3 }
Output : 5

Input :
Size of array  :  n = 12
Array elements :  arr[n] =
{ -3 , -3 , -7 , -7 , -1 , -7 , 3 , 3 , -2 , -1 , 0 , -7 }
Output : 5

Explanation : In Example 1 we have array {4  , -4 , 1 , -3 , 1 , -3 }.

The maximum length of subsequence we can have is 5 and the subsequence will be 4 1 -3 1 -3.

We can see that sum of elements from left to right is never less than 0 at any point.

Similarly for example 2 array { -3 , -3 , -7 , -7 , -1 , -7 , 3 , 3 , -2 , -1 , 0 , -7 }.

The maximum length of subsequence we can have is 5 and the subsequence could be 3  3  -2  -1  0.

Algorithm :

1. We will maintain a variable s to store the sum of subsequence element till now and a priority queue to store the elements inserted so far in the subsequence with the smallest element at the top.
2. If on adding an element the sum becomes less then 0 we remove the smallest element (most negative element) from the queue and subtract it from our current sum.
3. We keep subtracting it till either our queue is empty or sum becomes more than zero.
4. The maximum length would be the length of our queue at the end.

Implementation :

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int arr[n];
    for(int i=0;i<n;i++)
    {
      cin>>arr[i];
    }
    priority_queue< int, vector<int>,greater<int> >pq;
    int S = 0;

    for (int i = 0; i < n; i++) {
        S += arr[i];
        pq.push(arr[i]);
        while (S < 0) {
            S -= pq.top();
            pq.pop();
        }
    }
    cout <<pq.size()<<endl;
    return 0;
}

Time Complexity : O(nlog(n))