Buy-sell Stock

September 02, 2022

1 - Buy-sell once

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int notHave = 0;
        int have = -prices[0];
        for(int i = 1; i < prices.size(); i++){
            notHave = max(notHave, have + prices[i]);
            have = max(have, 0 - prices[i]);
        }
        return notHave;
    }
};

2 - Buy-sell infinite times

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int notHave = 0;
        int have = -prices[0];
        for(int i = 1; i < prices.size(); i++){
            notHave = max(notHave, have + prices[i]);
            have = max(have, notHave - prices[i]);
        }
        return notHave;
    }
};

3 - Buy-sell infinite times with cooldown

• 309. Best Time to Buy and Sell Stock with Cooldown
  • 1 day cooldown to buy again
  • need understand why dp[having stock on day i] is dp[i-2][notHave]
  • remember start at i = 2

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 1){
            return 0;
        }
        int notHave = 0;
        int have = -prices[0];
        int prev = 0;
        notHave = max(0, have + prices[1]);
        have = max(-prices[1], have);
        for(int i = 2; i < prices.size(); i++){
            int temp = notHave;
            notHave = max(notHave, have + prices[i]);
            have = max(have, prev - prices[i]);
            prev = temp;
        }
        return notHave;
        
    }
};

4 - Buy-sell k_max times

• If k_max exceeds half the size, return maxProfitInf
• Remember to initialize the base case of i = 0

class Solution {
public:
    int maxProfit(int k_max, vector<int>& prices) {
        if(prices.size() <= 1){
            return 0;
        }
        if(k_max > prices.size()/2){
            return maxProfitInf(prices);
        }
        
        vector<vector<vector<int>>>dp (prices.size(), vector<vector<int>>(k_max+1, vector<int>(2, 0)));
        for(int k = 1; k <= k_max; k++){
            dp[0][k][1] = -prices[0];
        }
        
        for(int i = 1; i < prices.size(); i++){
            for(int k = 1; k <= k_max; k ++){
                dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
                dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
            }
               
        }
        return dp[prices.size()-1][k_max][0];
    }
};