Linear time. Easy understand. With detailed explanation.


  • 0
    C

    Hope this helps.

    • buy_day the day when we buy stock produces current max_profit
    • loop
    • calcute current profit and if necessary update max_profit, and if current price is lower than buy_day's price, update buy_day
    • until the last day
        int maxProfit(vector<int>& prices)
        {
            int size = prices.size();
            int max_profit = 0, buy_day = 0;
            for(int i = 1; i < size; ++i)
            {
                max_profit = max(max_profit, prices[i] - prices[buy_day]);
                if(prices[i] < prices[buy_day])
                    buy_day = i;
            }
            
            return max_profit;
        }
    

Log in to reply
 

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