I know it's right, my code is accepted. But how to prove this method is mathmetically right ?
How do you feel right now ?
I'm confusing on the same question !!!
How could we know the selling price before buying ??
Consider first a contiguous subsequence of increasing prices.
The profit-maximizing strategy within this subsequence is to buy on the first day and sell on the last day
because this is the only strategy that realizes all of the day-to-day gains within the subsequence.
Notice further that the entire sequence can be decomposed into a series of
maximally-sized contiguous subsequences of increasing prices, some of which might be trivial, i.e., of length 1.
It never makes sense to buy in one such subsequence A and then sell in a following subsequence B, since we could
always do better by inserting a sale at the end of A and a buy at the beginning of B.
Therefore profit can be maximized by identifying each maximally-sized contiguous subsequence of increasing prices,
and buying at the beginning of it and selling at the end of it.
However, there is more to the story!
Because this strategy realizes all of the day-to-day gains within each subsequence, and we have described how
the entire sequence can be decomposed into such subsequences, it follows that this strategy
realizes all of the day-to-day gains within the entire sequence.
Since we are only asked to return the total profit and not the actual transaction log,
it suffices to sum together the day-to-day gains across the entire sequence.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.