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
Copy 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
Copy 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])
Copy 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
Copy 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])
Copy 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 ];
}
Copy 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;
}