Problems
Best Time to Buy and Sell Stock 2
Best Time to Buy and Sell Stock 2
You are given an array of prices, where $prices_i$ contains the price of a stock on the $i$-th day.
Each day, you can decide whether to buy and/or sell stocks. At any given time, you can own at most one stock.
Find the maximum profit that can be obtained.
\InputFile
The first line contains the size $n~(n \le 10^5)$ of the price array. The second line contains the price array - $n$ integers, each not exceeding $10^4$.
\OutputFile
Print the maximum profit that can be obtained. If it is impossible to obtain a profit, output $0$.
\includegraphics{https://eolympusercontent.com/images/80h7dad3dp3kfebfgcr544adtk.gif}
Input example #1
8 6 3 6 4 2 4 8 3
Output example #1
9
Input example #2
4 5 5 3 2
Output example #2
0