Cpp dp, using O(k) space to avoid runtime error


  • 0
    L
    class Solution {
    public:
        int maxProfit(int k, vector<int>& prices) {
            // maxProfit(k,j) = max(maxProfit(k, j-1), maxProfit(k-1,i) + profit[j]-profit[i])
            int n = prices.size();
    
            vector< vector<int> > profit(2, vector<int>(n,0));
            int result = 0;
            
            if(k>=n/2) {
                for(int i=1;i<n;++i) {
                    int value = prices[i] - prices[i-1];
                    result += value>0?value:0 ;
                }
                return result;
            }
            
            for(int i=1;i<=k;++i) {
                
                int cur = i%2;
                int prev = cur==1 ? 0 : 1;
                
                int curEstimateProfit = profit[prev][0] - prices[0];
                for(int j=1;j<n;++j) {
                    profit[cur][j] = max(profit[cur][j-1], prices[j] + curEstimateProfit);
                    curEstimateProfit = max(curEstimateProfit, profit[prev][j] - prices[j]);
                }
            }
            
            return profit[k%2][n-1];
            
            
        }
    };

Log in to reply
 

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