Best time to buy and sell stock

One pass, one buy and one sell: track the lowest price seen so far and the best profit it could unlock.

The idea

You must buy before you sell, so walk the prices once remembering the lowest price seen so far. At every later day, check whether selling there would beat the best profit found yet; there is no need to track the actual buy day, only the running minimum.

Code

public static int MaxProfit(int[] prices) {
    int minPrice = prices[0], best = 0;
    for (int i = 1; i < prices.Length; i++) {
        if (prices[i] < minPrice) minPrice = prices[i];
        else best = Math.Max(best, prices[i] - minPrice);
    }
    return best;
}

Tips

• A new minimum price can never itself be a profitable sell day, so the two updates never both fire on the same day.
• The running-minimum idea here is the same shape as the Kadane algorithm for maximum subarray sum.

In the .NET library

Checking every buy-sell pair is O(n²); carrying just the running minimum forward turns it into one O(n) pass.