An orbital research station tracks its oxygen reserve as a single running total, starting at exactly 0 units at the beginning of the mission log. Mission control has a fixed schedule of n events listed in chronological order; event i changes the reserve by delta[i] units, where a positive delta represents a resupply pod docking and adding oxygen, and a negative delta represents a scheduled system draw removing oxygen. Life-support regulations require that the reserve never be allowed to fall below zero at any point.
Because some scheduled events are optional, mission control may pre-cancel any subset of them before the mission begins. The events that are NOT cancelled ("honored") are then applied to the reserve strictly in their original chronological order, skipping straight over the cancelled ones (whose deltas are simply never applied). Mission control wants to honor as many events as possible while guaranteeing the reserve is never negative immediately after any honored event.
Given the full schedule, determine the maximum number of events that can be honored.
A single integer: the maximum number of events that can be honored without the reserve ever going negative.
Example 1
Input
5 2 -5 3 -1 -2
Expected
4
Explanation
Honoring all 5 events would take the reserve 0 -> 2 -> -3, violating the floor. Cancelling the -5 event instead gives the honored sequence [2, 3, -1, -2] with reserve 0 -> 2 -> 5 -> 4 -> 2, never negative, honoring 4 of the 5 events -- the best possible.
Example 2
Input
3 -1 -2 -3
Expected
0
Explanation
Every event is a net draw and the reserve starts at 0, so honoring even a single one immediately drives the reserve negative (0 + (any of them) < 0). No event can be honored, so the answer is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →