Sharing my 8ms C++ solution


  • 1
    T
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int n = prices.size();
            if(n<=1)
                return 0;
            
            vector<int> DPnostock(n);
            vector<int> DPyesstock(n);
            
            DPnostock[0] = 0;
            DPyesstock[0] = -prices[0];
            
            DPnostock[1] = max(0, prices[1]-prices[0]);
            DPyesstock[1] = max(-prices[1], -prices[0]);
            
            for(int i=2; i<n; i++)
            {
                DPnostock[i] = max(prices[i]+DPyesstock[i-1], DPnostock[i-1]);
                DPyesstock[i] = max(DPyesstock[i-1], DPnostock[i-2]-prices[i]);
            }
            
            return DPnostock[n-1];
        }
    };

Log in to reply
 

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