121_best_time_to_buy_and_sell_stock.cc

#include <vector>
 
using vi = std::vector<int>;
 
class Solution {
public:
    int maxProfit(vi& prices) {
        if (prices.size() == 1) return 0;
 
        int left = 0, right = 1, maxProfit = 0;
 
        while (right < prices.size()) {
            int profit = prices[right] - prices[left];
            if (profit > maxProfit) maxProfit = profit;
 
            // When prices[right] < prices[left], then right is at the global minimum
            // any index between the old left and right cannot have a lower price, otherwise
            // left woud have been updated earlier as evident below.
            // So setting left = right would not discard any optimal solution.
            if (profit < 0) left = right;
            else right++;
        }
 
        return maxProfit;
    }
};