ith element is the price of a given stock on day i.
- You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
- After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
so, it's like a dynamic programming? how about f[i] is we buy in ith day, the maximum profit?
I don't know...let me see the std's solution.
these problem is a similar problem...we can use three array to record the information we need.
buy[i] means we bought a stock before ith day's maximum profit.
sell[i] means we sold a stock before ith day's maximum profit.
rest[i] means we are coll down in ith day's maximum profit.
buy[i] = max(rest[i-1] - price, buy[i-1]), sell[i] = max(buy[i-1] + price, sell[i-1]), rest[i] = max(sell[i-1], buy[i-1], rest[i-1])
It's too complicated to understand the solution.
It's just a assumption. If we face these problems agian, can we design these states?
also, we know rest[i] = sell[i-1]; we can simply our relationships into buy[i] = max(sell[i-2] - price, buy[i-1]), sell[i] = max(buy[i-1] + price, sell[i-1]).
It's a classical dp question. I still need to learn more about the DP!