C++ 6ms (100%) solution (not DP)


  • 0
    C
        int maxProfit(vector<int>& prices) {
            int size = prices.size();
            if (prices.size() <= 1) {
                return 0;
            }
            
            // trans1MaxProfit[i]: starting from day0, ending at dayi, max profit
            // trans2MaxProfit[i]: starting from dayi+1, ending at final day, max profit
            // i = size - 1 means there is no trans2, all profits from trans1.
            vector<int> trans1MaxProfit(size);
            vector<int> trans2MaxProfit(size);
            
            int minPrice = prices[0];
            int maxProfit = 0;
            for (int i = 1; i < size; i++) {
                if (prices[i] > minPrice) {
                    int profit = prices[i] - minPrice;
                    if (profit > maxProfit) {
                        maxProfit = profit;
                    }
                } else {
                    minPrice = prices[i];
                }
                trans1MaxProfit[i] = maxProfit;
            }
            
            int maxSellPrice = prices[size - 1];
            maxProfit = 0;
            for (int i = size - 2; i >= 1; i--) {
                if (prices[i] >= maxSellPrice) {
                    maxSellPrice = prices[i];
                } else {
                    int profit = maxSellPrice - prices[i];
                    if (profit > maxProfit) {
                        maxProfit = profit;
                    }
                }
                // according to definition, trans2MaxProfit[i] starts from day i+1
                trans2MaxProfit[i - 1] = maxProfit;
            }
            
            // add up trans1 and trans2 to find out the max
            maxProfit = 0;
            for (int i = 0; i < size; i++) {
                int sum = trans1MaxProfit[i] + trans2MaxProfit[i];
                if (sum > maxProfit) {
                    maxProfit = sum;
                }
            }
            return maxProfit;
        }
    

Log in to reply
 

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