Sunday, June 12, 2016

309. Best Time to Buy and Sell Stock with Cooldown

We need to keep the profit of buying stock and the profit of selling stock.
When we buy stock, our profit will be subtracted by the price. When we sell stock, our profit will be added by the price. So we have following equations on day i:
For profit of buying stock, we have:
case 1: we sell stock on day i-2, and buy on day i;
case 2: we keeps the stock from day i-1 and do nothing on day i;
profitHasStock = max(profitNoStock[i-2]-prices[i], profitHasStock[i-1]);

For profit of selling stock, we have:
case 1: we have no stock on day i-1 and still do nothing on day i;
case 2: we have stock on day i-1, and sell stock on day i;
profitNoStock[i] = max(profitNoStock[i-1], profitHasStock[i-1]+prices[i]);


1:  class Solution {  
2:  public:  
3:    int maxProfit(vector<int>& prices) {  
4:      int n = prices.size();  
5:      if (n == 0 || n == 1) return 0;  
6:      // profitHasStock[i] indicates maximum profit with stock at hand on day i;  
7:      // note, the profit can be negative with stock at hand.  
8:      vector<int> profitHasStock(n, 0);  
9:      // profitNoStock[i] indicates maximum profit with no stock at hand on day i;  
10:      // obviously, we must sell all stocks on day n, so profitNoStock[n] will be the result.  
11:      vector<int> profitNoStock(n, 0);  
12:      profitHasStock[0] -= prices[0];  
13:      profitNoStock[1] = max(profitHasStock[0]+prices[1], profitNoStock[0]);  
14:      profitHasStock[1] = max(profitHasStock[0], profitNoStock[0]-prices[1]);  
15:      for (int i = 2; i < prices.size(); i++) {  
16:        profitHasStock[i] = max(profitNoStock[i-2]-prices[i], profitHasStock[i-1]);  
17:        profitNoStock[i] = max(profitNoStock[i-1], profitHasStock[i-1]+prices[i]);  
18:      }  
19:      return profitNoStock[n-1];  
20:    }  
21:  };  

No comments:

Post a Comment