You are given an integer array transactions, where transactions[i] represents the amount of the ith transaction:
The account starts with a balance of 0, and the balance must never become negative. Transactions must be considered in the given order, but you are allowed to skip some transactions.
Return an integer denoting the maximum number of transactions that can be performed without the balance ever going negative.
Example 1:
Input: transactions = [2,-5,3,-1,-2]
Output: 4
Explanation:
One optimal sequence is [2, 3, -1, -2], balance: 0 → 2 → 5 → 4 → 2.
Example 2:
Input: transactions = [-1,-2,-3]
Output: 0
Explanation:
All transactions are negative. Including any would make the balance negative.
Example 3:
Input: transactions = [3,-2,3,-2,1,-1]
Output: 6
Explanation:
All transactions can be taken in order, balance: 0 → 3 → 1 → 4 → 2 → 3 → 2.
Constraints:
1 <= transactions.length <= 105-109 <= transactions[i] <= 109We use an ordered set (such as C++'s multiset, Java's TreeMap, Python's SortedList) to store the selected transaction amounts, and maintain a variable s to record the current balance. Initially s=0, and the answer ans is initialized to the number of transactions.
Then we traverse each transaction amount x:
x to the balance s and add x to the ordered set.s becomes negative at this point, it means some negative amounts among the currently selected transaction amounts have caused insufficient balance. To retain as many transactions as possible, we should remove the smallest amount among the currently selected transaction amounts (because removing the smallest amount can maximize the balance). We remove the smallest amount y from the ordered set, subtract y from the balance s, and decrement the answer ans by 1.s is no longer negative.After traversal is complete, the answer ans is the maximum number of transactions that can be performed.
The time complexity is O(n times log n), where n is the number of transactions. The space complexity is O(n).
Java
C++
Go
Practice Maximum Transactions Without Negative Balance with our built-in code editor and test cases.
Practice on FleetCode