GreedyArrayDynamic Programming
You are given the price of a stock on each day. You may buy and sell as many times as you like, but you can hold at most one share at a time (sell before you buy again). Find the maximum total profit.
Input
Line 1: n. Line 2: n prices.
Output
Print the maximum profit.
Constraints
1 <= n <= 10^5 0 <= price <= 10^4
Example 1
Input
6 7 1 5 3 6 4
Output
7
Buy at 1 sell at 5 (+4), then buy at 3 sell at 6 (+3).
Example 2
Input
5 5 4 3 2 1
Output
0
Prices only fall, so there is no profit.