loading...
Cover image for Record fraud (find an algorithm)

Record fraud (find an algorithm)

hkrogstie profile image Håvard Krogstie Updated on ・1 min read

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 of hisory
  • 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)

Posted on Jun 6 by:

hkrogstie profile

Håvard Krogstie

@hkrogstie

Played around with programming in different languages over the years. Trying to unlearn old habits while keeping those worth keeping. Doing algorithms contests, bronze medal from IOI.

Discussion

markdown guide