A share has a known price on each of n consecutive days. You may buy and sell as many times as you like, but you may hold at most one share at a time: you must sell the share you hold before buying again. Buying and selling on the same day is not allowed (a sale happens on a later day than its buy).
Return the maximum total profit over the whole period.
Line 1: an integer n, the number of days.
Line 2: n space-separated non-negative integers, the daily prices (present whenever n >= 1).
A single integer: the maximum total profit achievable, or 0 if no profit is possible.
Example 1
Input
6 7 1 5 3 6 4
Expected
7
Explanation
Buy at 1 and sell at 5 (profit 4), then buy at 3 and sell at 6 (profit 3). Total 7, the sum of both upward moves.
Example 2
Input
5 5 4 3 2 1
Expected
0
Explanation
Prices only fall, so any trade loses money. Doing nothing yields a profit of 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →