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; }