Description
Doraemon aims to make a fortune from the significant daily price changes of dorayakis. He plans to buy a dorayaki on one day and sell it on another to profit from the price spread. To keep his plan secret, Doraemon will only hold one dorayaki at a time, meaning he must sell each one before buying another.
Given the dorayaki prices over a continuous span of N days, please calculate the maximum profit Doraemon can gain.
Example
N = 8 days, prices = [7, 2, 5, 6, 3, 8, 1, 9]
Buy on day 2 (-2) -> Sell on day 4 (+6) -> Buy on day 5 (-3) -> Sell on day 6 (+8) -> Buy on day 7 (-1) -> Sell on day 8 (+9)
Maximum profit = (-2) + 6 + (-3) + 8 + (-1) + 9 = 17
Input
- The first line contains an integer N (1 ≤ N ≤ 105), representing the number of days.
- The second line contains N integers: x1, x2, ..., xN (1 ≤ xi ≤ 109), where xi represents the price of dorayakis on the i-th day.
Output
Output a single line containing one integer — the maximum profit Doraemon can gain.
Constraints
- 60% - N ≤ 20. Use recursion to enumerate all kinds of ways to conduct transactions and return the maximum profit that can be gained.
- 40% - N ≤ 105. Try to think about what we can do with "unlimited transactions".