Question
The Merchant of Time
Chrono Market is a marketplace where stock prices from different days are visible at once. The prices change daily, and Arin wants to make as much profit as possible by buying and selling stocks these days.
You are given an array of integers representing the price of a stock over n days, where prices[i] is the price on the i-th day.
Arin can make multiple transactions (buy one and sell one share of the stock multiple times). However, Arin can hold at most one share at a time.
They are also allowed to buy and sell on the same day if it’s profitable.
Determine the maximum total profit Arin can achieve.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the number of days.
The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression — representing the stock prices on each day.
The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression — representing the stock prices on each day.
Output
Print a single integer — the maximum profit Arin can earn.
Example
Input
6
7 1 5 3 6 4
Output
7
Explanation
Arin can follow this strategy:
Buy on day 2 (price = 1), sell on day 3 (price = 5), profit = 4
Buy on day 4 (price = 3), sell on day 5 (price = 6), profit = 3
Total profit = 4 + 3 = 7
6
7 1 5 3 6 4
Output
7
Explanation
Arin can follow this strategy:
Buy on day 2 (price = 1), sell on day 3 (price = 5), profit = 4
Buy on day 4 (price = 3), sell on day 5 (price = 6), profit = 3
Total profit = 4 + 3 = 7