Loading...
Loading...
Loading...
Rohan practises trading in a college finance club game. He knows the price of one share for each of the next n days.
He can hold at most one share at a time. On each day he can buy one share (if he holds none), sell his share (if he holds one) or do nothing. After a day on which he sells, he must rest the next day: he cannot buy on that day.
He starts with no share. Print the most profit he can make. A share he never sells earns nothing.
Example 1
Input
5 1 2 3 0 2
Output
3
Buy at 1, sell at 2, rest on the day of price 3, buy at 0, sell at 2. The profit is 1 + 2 = 3.
Example 2
Input
4 9 7 4 1
Output
0
The price only falls, so the best is to never buy.
Try the problem first. Open one hint at a time.
At the end of each day Rohan is in one of three states: holding a share, just sold today, or resting with no share.
Keep the best profit for each state on each day. Holding today means he held yesterday, or he was resting yesterday and buys today.
Just sold today means he held yesterday and sells at today's price. Resting today means he rested or sold yesterday.
On day 1, holding means he paid that day's price. The answer is the better of "just sold" and "resting" on the last day.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor