Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Solution: One Pass O(n) time.

For each day i,

1. think of if sell it at day i, compare the profit with maxProfit.

2. check if day i is a better day than any previous day to buy a stock, meaning the price is cheaper than any previous day, then we buy the stock at day i.

public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) {
        return 0;
    }
    int maxProfit = 0;
    int sum = 0;
    int buyDate = 0;
    for (int i = 1; i < prices.length; i++) {
        maxProfit = Math.max(maxProfit, prices[i] - prices[buyDate]);
        if (prices[i] < prices[buyDate]) {
            buyDate = i;
        }
    }
    return maxProfit;
}

Share