188. Best Time to Buy and Sell Stock IV - cocoder39/coco39_LC GitHub Wiki

188. Best Time to Buy and Sell Stock IV

solution 1: extension from 53. Maximum Subarray

initial idea would be profit[i][j] = max(profit[i – 1][j], profit[i – 1][j – 1] + diff). However, it is incorrect because if there are transactions on both day i - 1 and day i, profit[i – 1][j – 1] + diff means selling on day i - 1, buying on day i - 1 then selling on day i. It is equal to profit[i][j - 1], rather than profit[i][j]

  • local[i][j] is max profit till day i with j transactions and transaction j happens exactly on day i

  • global[i][j] is max profit till day i with j transactions

  • local[i][j] comes from two sources: if sell on day i - 1 and buy on day i can make profit (diff > 0), we can take global[i][j - 1] + diff into consideration. Also, we can get it from local[i - 1][j].

  • global[i][j] comes from global[i - 1][j] and local[i][j]

O(kn) time and O(kn) space

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int sz = prices.size();
        if (sz == 0)    return 0;
        if (sz <= k)    return cornercase(prices);
        vector<vector<int>> local(sz, vector<int>(k + 1)); //local[i][j] max profit till day i && transaction j where j happens on i
        vector<vector<int>> global(sz, vector<int>(k + 1)); //global[i][j] max profit till day i && tansaction j
        
        for (int i = 1; i < sz; i++) {
            int diff = prices[i] - prices[i - 1];
            for (int j = 1; j <= k; j++) {
                //tran j on day i: (1) tran j - 1 before day i (2) tran j on day i - 1, lets retry tran j on day i
                local[i][j] = diff > 0 ? max(global[i - 1][j - 1] + diff, local[i - 1][j] + diff) : local[i - 1][j] + diff;
                global[i][j] = max(global[i - 1][j], local[i][j]);
            }
        }
        return global[sz - 1][k];
    }
private:    
    int cornercase(vector<int>& prices) {
        int res = 0;
        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] > prices[i - 1])
                res += prices[i] - prices[i - 1];
        }
        return res;
    }
};

solution 2: an extension from [123. Best Time to Buy and Sell Stock III] (https://github.com/PuChen0211/leetcodeNote/wiki/123.-Best-Time-to-Buy-and-Sell-Stock-III), update transaction from k to 1. When k is very large (eg. 10,000,000), the problem is reduced to 122. Best Time to Buy and Sell Stock II

O(kn) time and O(k) space

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int sz = prices.size();
        if (sz == 0) {
            return 0;
        }
        if (sz / 2 <= k) { //very time consuming if k is large, reduce to stockII when k is greater than sz
            return stockII(prices);
        }
        
        vector<int> sell(k + 1);
        vector<int> buy(k + 1, INT_MIN);
        
        for (int i = 0; i < prices.size(); i++) {
            for (int j = k; j >= 1; j--) {
                sell[j] = max(sell[j], buy[j] + prices[i]);
                buy[j] = max(buy[j], sell[j - 1] - prices[i]);
            }
        }
        return sell[k];
    }
private:    
    int stockII(vector<int>& prices) {
        int res = 0;
        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] > prices[i - 1]) {
                res += prices[i] - prices[i - 1];
            }
        }
        return res;
    }
};

more awesome solutions

⚠️ **GitHub.com Fallback** ⚠️