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.erase(s.begin());
        s.insert(c); //insert second copy for SECOND CHOICE
    }
}
return ans;

The solution is really short, which makes it all the more frustrating that I can't prove it.

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.