Difficulty: Beginner
You work in a start up with very unstable finances. You have a chronological list of all income (positive integers) and expenses (negative integers), and you need to share it with investors.
However, you don't want the busines to appear unprofitable. In fact, you want it to seem as if the busines has never been in the red ever. You do this by selectively removing expenses from the list, removing as few as possible to avoid rasing suspicion.
What does the list given to the investors look like?
Input
An array of integers history
Output
An array of integers cleared
where
-
cleared
is a subsequece ofhisory
-
sum(cleared[:n])
is non-negative for all n -
len(cleared)
is maximized
If multiple outputs fulfill the requirements, return any one of them
Constraints
len(history) <= 100 000
abs(history[i]) <= 10^9
Example
Input
[-3, 8, -4, -5, 4, -2, -3, -2, -2, 5, -6, 2, -5, -5]
Possible output
[8, 4, -2, -3, -2, -2, 5, 2, -5, -5]
Try to make an algorithm that's O(n log n)
Top comments (0)