Dynamic programming with C++ implementation


  • 1
    T
    class Solution {
    private:
        int maxProfitHelper(int k, vector<int> prices) {
            int n = prices.size();
            if(n<=1 || k<1)
                return 0;
    
            int temp = 0;
            int count = 0;
            int i;
            for(i=1; i<n; i++)
            {
                if(prices[i] - prices[i-1] > 0)
                {
                    temp = temp + prices[i] - prices[i-1];
                    count = count + 1;
                }
            }
    
            if(count < k)
                return temp; // When k is big, dynamic programming might become time consuming
    
            // Dynamic programming
            vector<int> curProfit(n, 0);
            vector<int> preProfit(n, 0);
    
            int lowCost;
            int j;
            for(j=0; j<k; j++)
            {
                lowCost = prices[0];
                for(i=1; i<n; i++)
                {
                    if(curProfit[i-1] < prices[i] - lowCost)
                        curProfit[i] = prices[i] - lowCost;
                    else
                        curProfit[i] = curProfit[i-1];
    
                    if(prices[i]-preProfit[i-1] < lowCost)
                        lowCost = prices[i]-preProfit[i-1];
                }
                preProfit = curProfit;
            }
            return curProfit[n-1];
        }
    public:
        int maxProfit(vector<int>& prices) {
            return maxProfitHelper(2, prices);
        }
    };

Log in to reply
 

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