C++ implementation, dynamic programming


  • 1
    T
    class Solution {
    public:
        int maxProfit(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];
        }
    };

  • 0
    A

    Your code looks really neat. Could you please give me some intuition about your dynamic programming ?


  • 0
    R

    The only problem of understanding is the meaning of variable "lowCost". This variable is to determine a possible start of a new transaction. As we know, a new Transaction is possible to gain more profit only when the current price is lower than the previous price. In the previous situation, the profit at that point is the same as the previous point. The minus is help to find the minimum point below the even line of profit of the previous situation.


  • 0
    R

    The only problem of understanding is the meaning of variable "lowCost". This variable is to determine a possible start of a new transaction. As we know, a new Transaction is possible to gain more profit only when the current price is lower than the previous price. In the previous situation, the profit at that point is the same as the previous point. The minus is help to find the minimum point below the even line of profit of the previous situation.


Log in to reply
 

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