3ms C++ solution, using bottom-up DP with O(k) space


  • 0
    G
    int maxProfit(int k, vector<int>& prices) {
            int n = prices.size();
            
            // Nothing to sell
            if (n <= 1) return 0;
            
            // Avoid using too many memory
            if (k > n / 2) {
                int ret = 0;
                for (int i = 1; i < n; i++) {
                    ret += max(prices[i] - prices[i - 1], 0);
                }
                return ret;
            }
            
            // Here we use the general dp solution, with one dimension array
            // Fill the table bottom-up
            int l[k + 1] = {0};
            int g[k + 1] = {0};       
    
            int gtemp = 0;
            for (int i = 1; i < n; i++) {
                int diff = prices[i] - prices[i - 1];
                for (int j = 1; j <= k; j++) {
                    l[j] = max(gtemp + max(diff, 0), l[j] + diff);
                    gtemp = j == k ? 0 : g[j];
                    g[j] = max(l[j], g[j]);
                }
            }
            return g[k];
        }
    

Log in to reply
 

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