A DP solution in C++, but seems slow...


  • 0
    G
    class Solution {
    public:
    	int maxProfit(vector<int>& prices) 
    	{
    		if (prices.size() == 0) return 0;
    		vector<int> dp(prices.size(), 0);
    
    		for (int i = 1; i < prices.size(); i++)
    		{
    			int max = dp[i-1];
    			for (int k = i; k >= 0; k--)
    			{
    				int d = prices[i] - prices[k];
    				if ( d>= 0)
    				{
    					int m = d;
    					if (k - 2 >= 0)
    					{
    						m = d + dp[k - 2];
    					}
    
    					if (m > max) max = m;
    				}
    			}
    
    			dp[i] = max;
    		}
    
    		return dp[prices.size()-1];
    	}
    };

  • 0

    It can be done in O(n) time with O(1) space.


Log in to reply
 

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