Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions: 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) Example: prices = [1, 2, 3, 0, 2] maxProfit = 3 transactions = [buy, sell, cooldown, buy, sell]
参考了:https://leetcode.com/discuss/71391/easiest-java-solution-with-explanations
1. Define States
To represent the decision at index i:
buy[i]
: Max profit till index i. The series of transaction is ending with a buy.sell[i]
: Max profit till index i. The series of transaction is ending with a sell.
To clarify:
- Till index
i
, the buy / sell action must happen and must be the last action. It may not happen at indexi
. It may happen ati - 1, i - 2, ... 0
. - In the end
n - 1
, returnsell[n - 1]
. Apparently we cannot finally end up with a buy. In that case, we would rather take a rest atn - 1
. - For special case no transaction at all, classify it as
sell[i]
, so that in the end, we can still returnsell[n - 1]
. Thanks @alex153 @kennethliaoke @anshu2.
2. Define Recursion
buy[i]
: To make a decision whether to buy ati
, we either take a rest, by just using the old decision ati - 1
, or sell at/beforei - 2
, then buy ati
, We cannot sell ati - 1
, then buy ati
, because of cooldown.sell[i]
: To make a decision whether to sell ati
, we either take a rest, by just using the old decision ati - 1
, or buy at/beforei - 1
, then sell ati
.
So we get the following formula:
buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
3. Optimize to O(1) Space
DP solution only depending on i - 1
and i - 2
can be optimized using O(1) space.
- Let
b2, b1, b0
representbuy[i - 2], buy[i - 1], buy[i]
- Let
s2, s1, s0
representsell[i - 2], sell[i - 1], sell[i]
Then arrays turn into Fibonacci like recursion:
b0 = Math.max(b1, s2 - prices[i]);
s0 = Math.max(s1, b1 + prices[i]);
4. Write Code in 5 Minutes
First we define the initial states at i = 0
:
- We can buy. The max profit at
i = 0
ending with a buy is-prices[0]
. - We cannot sell. The max profit at
i = 0
ending with a sell is0
.
1D Array: better to understand:
1 public class Solution { 2 public int maxProfit(int[] prices) { 3 if (prices==null || prices.length<=1) return 0; 4 int[] buy = new int[prices.length]; 5 int[] sell = new int[prices.length]; 6 buy[0] = -prices[0]; 7 sell[0] = 0; 8 for (int i=1; i<prices.length; i++) { 9 buy[i] = Math.max(buy[i-1], -prices[i] + ((i>=2)? sell[i-2] : 0)); 10 sell[i] = Math.max(sell[i-1], buy[i-1] + prices[i]); 11 } 12 return sell[prices.length-1]; 13 } 14 }
Just few variables:(better)
1 public class Solution { 2 public int maxProfit(int[] prices) { 3 if (prices==null || prices.length<=1) return 0; 4 int b0 = -prices[0]; 5 int s0 = 0; 6 int b1 = b0; 7 int s1 = s0; 8 int s2 = 0; 9 for (int i=1; i<prices.length; i++) { 10 b0 = Math.max(b1, s2-prices[i]); 11 s0 = Math.max(s1, b1+prices[i]); 12 s2 = s1; 13 s1 = s0; 14 b1 = b0; 15 } 16 return s0; 17 } 18 }