Editorial for Perfect Test

Suppose Sean just went from left to right, including every question in the test that he is able to, and skipping those that he cannot. Why would this solution fail?

An input like 5 -5 -3 -2 is an example that would fail this intuition. By taking the -5 question, we make an inoptimal choice, as we could instead choose the -2 and -3 questions.

Let's try making a change to the greedy solution described above. Let's suppose we've greedily picked questions until we can no longer. And the next question is -3.

Under what conditions might it be optimal to take the -3 question, and change our previous decisions?

It would be better to take the -3 question if one of the previous questions we've taken is worse than -3. This then has us using the same number of questions, but the current student mark would be higher.

How can we quickly find the worst question we've included so far? This would help our greedy approach above.

If we greedily take the questions from left to right, and store their values in a min-heap, then we can very quickly query to find the worst question we have included so far.

If at any point our expected score would go negative, then we can check the worst question we've taken so far, and if this is worse than the prospective next question, we can remove it from the heap and add the next question instead. Since we are removing a negative question, and replacing it with a smaller one further along in the test, we are guaranteed that our previous selection is still valid, and our total never goes negative.