Simple and easy understood c++ code with O(n) time and O(n) space


  • 0
    X
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            if(prices.empty())
                return 0;
            int sellMax[prices.size()] = {0};
            int buyMax[prices.size()] = {0};
            //initial sellMax on everyday
            int minVal = prices[0];
            for(int i=1; i<prices.size(); i++){
                if(prices[i] > minVal)
                    sellMax[i] = prices[i] - minVal;
                else
                    minVal = prices[i];
            }
            //initial buyMax on everyday
            int maxVal = prices.back(), maxDis = 0;
            for(int i=prices.size()-2; i>=0; i--){
                if(prices[i] < maxVal){
                    buyMax[i] = maxVal - prices[i];
                    if(buyMax[i] > maxDis){
                        maxDis = buyMax[i];
                    }else
                        buyMax[i] = maxDis;
                }
                else{
                    maxVal = prices[i];
                    buyMax[i] = maxDis;
                }
            }
            //loop to find the max profit
            int maxPro = 0, tmpPro;
            for(int i=0; i<prices.size(); i++){
                tmpPro = sellMax[i];
                tmpPro += buyMax[i];
                if(tmpPro > maxPro)
                    maxPro = tmpPro;
            }
            return maxPro;
        }
    };

Log in to reply
 

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