You are given a record of the historical prices of an investment asset from the last N days. Analyze the record in order to calculate what could have been your maximum income. Assume you started with one asset of this type and could hold at most one at a time. You could choose to sell the asset whenever you held one. If you did not hold an asset at some moment, you could always afford to buy an asset (assume you had infinite money available).
What is the maximum income you could make?
Since that result may be very large, return its last nine digits without leading zeros (return the result modulo 1,000,000,000).
Ex1:
Input = [4,1,2,3]
Output = 6
Explanation: Sell @ 4, Buy @ 1, Sell @ 3Ex2:
Input = [1, 2, 3, 3, 2, 1, 5]
Output = 7
Explanation: Sell @ 3, Buy @ 1, Sell @ 5Ex3:
Input = [1000000000, 1, 2, 2, 1000000000, 1, 1000000000]
Output = 999999998
Explanation: Sell @ 1000000000, Buy @ 1, Sell @ 1000000000, Buy @ 1, Sell @ 1000000000
The maximum possible income is 2999999998, whose last 9 digits are 999999998Constraints
1 <= n <= 200000
0 <= arr[i] <= 1000000000Comments (2)