Time Travel in Greedy Algorithms
Given an array of positive integers, for each element, you can choose to multiply it by $-1$. Find the maximum number of negative elements at the end, such that the prefix sum of the final array contains strictly positive integers only.
An obviously incorrect algorithm is to greedily negate elements as long as the prefix sum stays positive, and skip the operation otherwise. Here’s a counter example.
arr = [11, 10, 1, 2, 4]
With this strategy, you can take
+11 -10 +1 +2 +4
We can see that the greedy strategy of choosing 10 immediately led us to lose the remaining 3 elements. If we were smart, we could’ve ignored the 10, and then negated 1, 2 and 4.
Now that you’ve convinced yourself that greedy doesn’t work, along with a counter example to back that claim, you are most likely to wander off thinking about complicated DP ideas.
But what if I told you that this Greedy algorithm can be fine tuned to be correct?
We need to ensure that we have done the best we can, not only in terms of accumulating the answers so far, but also maximizing our chances of increasing the answer in future.
Start iterating the elements from left to right. At the beginning, as long as it’s not possible to negate it, just keep adding it to the prefix sum. Obviously we have done the best so far.
Now, consider the 1st element where it’s possible to negate it. We will necessarily negate it, because we don’t want to lose out on the opportunity. But what if it turns out to be a bad decision in future? No worries, we’ll use time travel to come back to this element and revert the operation. Then, continue negating elements as far as possible.
Now, suppose we finally hit an element, negating which is not possible. Notice that, before this element, we had done the best we can in terms of count. Hence, we can only increase the answer by 1. We don’t have to overthink about taking $a[i]$ in our set, because that would mean removing at least one element from our previous set, which doesn’t really change anything.
So, if we can’t take $a[i]$, what else can we do? We can increase our chances for taking the upcoming elements. For this, we can use hindsight. If the maximum absolute value of the elements negated so far is $> a[i]$, we should return that element to the positive set, and negate $a[i]$ instead. This will increase the prefix sum, hence maximizing our chances.
We can use a heap to store the elements that have been negated so far.
You can now intuitively see why this algorithm is correct. Or you can try proving it in a formal manner. Might add the formal proof later!
For some Greedy problems, it helps to make the best decision possible at that time, but then, go back in time to improve your decisions.
If you are looking for a problem to test your understanding of this concept, here’s a recent problem from Atcoder Beginner Contest that uses this idea : ABC344F : Earn to Advance. Ask me for hints on any of these platforms.