stocks_dp.cpp

/*
This file organizes questions related to buying and selling
stocks
*/

/*
188. buy / sell stocks with transaction limit
buy (i,j): max profit on the ith day possible buy, total transaction limit
is j.
sell (i, j): max profit on the ith day possible sell, total transaction limit is j
note: for 1 transaction there are two operations buy and sell. let's record the
limit based on buy operation.(i.e., --j on buy)
So 4 possibilies are enumerated in two functions
buy(i, j) = max(sell(i-1, j-1) - prices[i], buy(i-1, j)) 
the first part: sell operation the day before, so we just buy today
the second part: holding today
sell(i, j) = max(buy(i-1, j) + prices[i], sell(i-1, j))
the first part: sell operation today, buy occurs some point before yesterday
the second part: holding today

initialization: max profit for buying on day 1 should be initialized to INT_MIN
illegal operations: day 1 we cannot sell
*/
int maxProfit(vector <int> prices, int k){
  //initialization 
  
  // core code
  for (int i = 1; i <= prices.size(); ++i){
    for (int j = 1; j <= k; ++j){
      buy[i][j] = max(sell[i-1][j-1] - prices[i-1], buy[i-1][j]);
      if (i > 1){
        sell[i][j] = max(buy[i-1][j] + prices[i-1], sell[i-1][j]);
      }
    }
  }
  return sell[prices.size()][k];
}

/*
309. buy sell stock with cooldown -- using state machine
track three states: sell; hold; reset
sell[i]: on the ith day sell the stock 
hold[i]: continue holding the current stock
reset[i]: initial config; or after a sell, the cooldown day that has no trans
See transition graph: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/solution/
*/
int maxProfit (vector <int> prices){
  
  for (int i = 1; i <= prices.size(); ++i){
    sell[i] = hold[i-1] + prices[i-1];
    hold[i] = max(hold[i-1], reset[i-1]-prices[i-1]);
    reset[i] = max(reset[i-1], sell[i-1]);
  }
  
  // optimize to constant space
  int sell = INT_MIN;
  int hold = INT_MIN;
  int reset = 0;
  for (int i = 0; i < prices.size(); ++i){
    int before_sell = sell;
    sell = hold + prices[i];
    hold = max(hold, reset - prices[i]);
    reset = max(reset, before_sell);
  }
  return max(sell, reset);
}

/*
714. buy sell with transaction fee -- using state machine
Same idea as above, set three states sell, hold and reset
Except there is a link from sell to buy directly
*/
int maxProfit (vector <int> prices) {
  vector <int> sell (prices.size()+1);
  vector <int> hold (prices.size()+1);
  vector <int> reset (prices.size()+1);
  sell[0] = INT_MIN+50000;
  sell[1] = INT_MIN+50000;
  hold[0] = INT_MIN+50000;
  reset[0] = 0;
  for (int i = 1; i <= prices.size(); ++i) {
    if (i > 1){
      sell[i] = hold[i-1]+prices[i-1]-fee;
    }
    hold[i] = max({hold[i-1], reset[i-1]-prices[i-1], sell[i-1]-prices[i-1]});
    reset[i] = max(reset[i-1], sell[i-1]);
  }
  return max(sell[prices.size()], reset[prices.size()]);
  
  // optimize to constant space
  int sell = INT_MIN;
  int hold = INT_MIN;
  int reset = 0;
  for (int i = 0; i < prices.size(); ++i){
    int before_sell = sell;
    sell = hold + prices[i]-fee;
    hold = max({hold, reset - prices[i], before_sell - prices[i]});
    reset = max(reset, before_sell);
  }
  return max(sell, reset);
}