O(n) time and O(1) space solution, no DP, 12ms


  • 0
    L
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int len = prices.size();
            if(len < 2) return 0;
            int ret = 0;
            for(int i = 0; i < 2; ++i){
                int profit = 0, minval = prices[0], minpos = 0, maxpos = 0, minposnow = 0;
                for(int j = 0; j < len; ++j){
                    if(prices[j] == -1 && j < len-1){
                        minposnow = j+1;
                        minval = prices[j+1];
                    }else if(prices[j] < minval){
                        minval = prices[j];
                        minposnow = j;
                    }else if(prices[j] - minval > profit){
                        profit = prices[j] - minval;
                        minpos = minposnow;
                        maxpos = j;
                    }
                }
                if(profit == 0) return ret;
                ret += profit;
                prices[minpos] = prices[maxpos] = -1;
                reverse(prices.begin() + minpos, prices.begin() + (++maxpos));
            }
            return ret;
        }
    };
    

    and it can be used to Best Time to Buy and Sell Stock IV too but will be really slow.


Log in to reply
 

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