My C++ solution with O(N) time 8ms


  • 0
    C

    my solution. With array 'maxDiffFirst' and 'maxDiffSecond' recording the max profit from the beginning and from the end respectively. And the max profit is therefore the max sum of maxDiffFirst[i] and maxDiffSecond[i+1].

     class Solution {
        public:
            int maxProfit(vector<int>& prices) {
                int L = prices.size();
                if( L<=1 )
                    return 0;
                // fisrt part
                vector<int> maxDiffFirst(L,0);
                int minBuy = prices[0];
                for( int i = 1; i<L; i++ ){
                    minBuy = minBuy<prices[i-1]? minBuy:prices[i-1];
                    maxDiffFirst[i] = maxDiffFirst[i-1]>prices[i]-minBuy? maxDiffFirst[i-1]:prices[i]-minBuy;
                }
                // second part
                vector<int> maxDiffSecond(L,0);
                int maxSell = prices[L-1];
                int ret = maxDiffFirst[L-1];
                for( int i = L-2; i>=0; i-- ){
                    maxSell = maxSell>prices[i+1]? maxSell:prices[i+1];
                    maxDiffSecond[i] = maxDiffSecond[i+1]>maxSell-prices[i]? maxDiffSecond[i+1]:maxSell-prices[i];
                    ret = ret>maxDiffSecond[i+1]+maxDiffFirst[i]? ret:maxDiffSecond[i+1]+maxDiffFirst[i];
                }
                ret = ret>maxDiffSecond[0]? ret:maxDiffSecond[0];
                return ret;
                
            }
        };

Log in to reply
 

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