What invariant is maintained in this solution?

Revision en1, by towrist, 2021-10-20 20:55:50

I was trying to solve 865D - Buy Low Sell High. When I gave up and saw the editorial, this is the idea presented [I am writing this in code form so that it is easy to understand]:

multiset<int> s;
int ans=0;

for (int c: arr) //for every integer in the input array
{
    s.insert(c); //insert one copy for FIRST CHOICE
    if (c>*s.begin())
    {
        ans+=c-*s.begin();
        s.insert(c); //insert second copy for SECOND CHOICE
    }
}
return ans;

I have an intuition on why it may work, but I am far from actually proving it.

I thought about it and if the algorithm is correct, at every iteration, ans actually stores the maximum profit that we can earn, if the array in the problem were upto that index.

However, I cannot prove the solution. I feel that if I get the invariant that is maintained in each iteration of the loop, it will help me prove that the algorithm actually outputs the maximum profit, up-to that iteration. By invariant, I mean, what can we say is true for the elements in the multiset for each step, that helps us prove the solution.

In short, I am asking for help to prove this solution properly. Any help will be appreciated.

Tags proof

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English towrist 2021-10-20 21:01:01 96
en2 English towrist 2021-10-20 20:57:51 29 Tiny change: ' s.' -> ' s.erase(s.begin());\n s.'
en1 English towrist 2021-10-20 20:55:50 1242 Initial revision (published)