CPP O(kn) time and O(k) space


  • 2

    This method is derived from III question and II question

    // O(kn) O(k)
    class Solution {
    public:
        int maxProfit(int k, vector<int>& prices) {
            if (prices.size() < 2 || k < 1) return 0;
            if (k > prices.size() / 2) return greedy(prices);
            vector<int> buy(k, INT_MIN), sell(k, 0);
            for (auto p : prices) {
                buy[0] = max(buy[0], -p);
                sell[0] = max(sell[0], buy[0] + p);
                for (int i = 1; i < k; i++) {
                    buy[i] = max(buy[i], sell[i - 1] - p);
                    sell[i] = max(sell[i], buy[i] + p);
                }
            }
            return sell[k - 1];
        }
    private:
        int greedy(vector<int>& prices) {
            int profit = 0;
            for (int i = 1; i < prices.size(); i++) {
                profit += (prices[i] > prices[i - 1]) ? (prices[i] - prices[i - 1]) : 0;
            }
            return profit;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.