State machine; C++; O(1) space; O(n) time


  • 0
    D
    class Solution 
    {
    	public:
    		int maxProfit(vector<int> &prices)
    		{	
    			size_t n = prices.size();
    			if (n <= 1)
    				return 0;
    
    			int prev_s0 = 0;
    			int prev_s1 = -prices[0];
    			int prev_s2 = -1e6;
    			int prev_s3 = -1e6;
    			int prev_s4 = -1e6;
    			
    			for (size_t idx = 1; idx < n; ++idx)
    			{
    				int s1 = max(prev_s1, prev_s0 - prices[idx]);
    				int s2 = max(prev_s2, prev_s1 + prices[idx]);
    				int s3 = max(prev_s3, prev_s2 - prices[idx]);
    				int s4 = max(prev_s4, prev_s3 + prices[idx]);
    				prev_s1 = s1;
    				prev_s2 = s2;
    				prev_s3 = s3;
    				prev_s4 = s4;				
    			}
    			
    			return max(prev_s4, max(prev_s2, prev_s0));
    		}
    };
    
    

Log in to reply
 

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