Buy and Sell Stock
121 I
You can only sell and buy once 1. mantain a profit
and low
int
122 II
You can buy and sell many times 1. greedy algo 2. if profitable, add on
public int maxProfit(int[] prices) {
int profit = 0;
for(int i=1; i<prices.length; i++){
if(prices[i] - prices[i-1] > 0){
profit += prices[i] - prices[i-1];
}
}
return profit;
}
123 III
You can only buy and sell twice 1. DP
public int maxProfit(int[] prices) {
int buy1 = - prices[0], buy2 = - prices[0];
int sell1 = 0, sell2 = 0;
for (int i=1; i<prices.length; i++){
// buy1每天都跟新購買比較
buy1 = Math.max(buy1, - prices[i]); // max profit of first buy
sell1 = Math.max(sell1, buy1 + price[i]); // max profit of first sell
buy2 = Math.max(buy2, sell1 - price[i]); // max profit of second buy
sell2 = Math.max(sell2, buy2 + price[i]); // max profit of second sell
}
return sell2;
}
188 IV
You can buy and sell for k times
Hold stock and unhold stock tables
State: 1. hold[i][j]: the max profit in ith day and j transaction with holding stock 2. unhold[i][j]: the max profit in ith day and j transaction without holding stock
Func: 1. hold[i][j] = max(hold[i-1][j], unhold[i-1][j]-price[i]) 2. unhold[i][j] = max(unhold[i-1][j], hold[i-1][j-1]+ price[i])
Init: hold[0][0-k] = - price[0], hold[i][0] = max(hold[i-1][0], -price[i])
Ans: unhold[len][k]
public int maxProfit(int k, int[] prices) {
int len = prices.length;
if (k >= len/2) return helper(prices);
// the max profit in ith day and k transaction with holding stock
int[][] hold = new int[len][k+1];
// the max profit in ith day and k transaction without holding stock
int[][] unhold = new int[len][k+1];
// init
for(int j=0; j<=k; j++){
hold[0][j] = -prices[0];
}
for(int i=1; i<len; i++){
hold[i][0] = Math.max(hold[i-1][0], -prices[i]);
}
// func
for(int i=1; i<len; i++){
for(int j=1; j<=k; j++){
hold[i][j] = Math.max(hold[i-1][j], unhold[i-1][j] - prices[i]);
unhold[i][j] = Math.max(unhold[i-1][j], hold[i-1][j-1] + prices[i]);
}
}
return unhold[len-1][k];
}
private int helper(int[] prices){
int profit = 0;
for(int i=1; i<prices.length; i++){
if(prices[i] - prices[i-1] > 0){
profit += prices[i] - prices[i-1];
}
}
return profit;
}
714 With transaction fee
You can buy and sell many times
public int maxProfit(int[] prices, int fee) {
// 2 situations: buy and sell
int buy = -prices[0];
int sell = 0;
for (int i=1; i<prices.length; i++){
buy = Math.max(buy, sell - prices[i]);
sell = Math.max(sell, buy + prices[i] - fee);
}
return sell;
}
309 With 1 day cool down
You can buy and sell many times
Func: buy[i] = max(buy[i-1], sell[i-2]-price[i]), sell[i] = max(sell[i-1], buy[i-1]+price[i])
O(n) space
public int maxProfit(int[] prices) {
public int maxProfit(int[] prices) {
if(prices == null || prices.length == 0) return 0;
int[] buy = new int[prices.length];
int[] sell = new int[prices.length];
buy[0] = -prices[0];
for(int i=1; i<prices.length; i++){
buy[i] = Math.max(buy[i-1], i == 1 ? -prices[i] : sell[i-2]-prices[i]);
sell[i] = Math.max(sell[i-1], buy[i-1]+prices[i]);
}
return sell[prices.length-1];
}
O(1) space
public int maxProfit(int[] prices) {
if(prices == null || prices.length == 0) return 0;
int buy = -prices[0];
int preSell = 0;
int curSell = 0;
for(int i=1; i<prices.length; i++){
int tmp = curSell;
buy = Math.max(buy, preSell - prices[i]);
curSell = Math.max(curSell, buy + prices[i]);
preSell = tmp;
}
return curSell;
}
Last updated
Was this helpful?