An easy to think of "recursive + memorize" solution.


  • 0
    W

    '''
    class Solution {
    public:
    int maxProfit(vector<int>& prices) {

        vector<int> m0(prices.size(), -1);
        vector<int> m1(prices.size(), -1);
    
        return recur(prices, 0, -1, m0, m1);
    }
    
    
    int recur(vector<int>& prices, int i, int hold, vector<int>& m0, vector<int>& m1)
    {
        if(i >= prices.size())
            return 0;
                
        int profit = 0;
        if(hold < 0)
        {
            return m0[i] > 0 ? m0[i] : (m0[i] = max(recur(prices, i + 1, prices[i], m0, m1), recur(prices, i + 1, hold, m0, m1))); 
        }
        else
        {  
            if(m1[i] > 0)
            {
                return m1[i] - hold;
            }
            
            profit = max(prices[i] - hold + recur(prices, i + 2, -1, m0, m1), recur(prices, i + 1, hold, m0, m1));
            m1[i] = profit + hold;
        }
        
        return profit;
    }
    

    };
    '''


Log in to reply
 

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