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.

Example 1:

1 2 3 4 5 |
Input: [7, 1, 5, 3, 6, 4] Output: 5 max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price) |

Example 2:

1 2 3 4 5 |
Input: [7, 6, 4, 3, 1] Output: 0 In this case, no transaction is done, i.e. max profit = 0. |

Analysis:

We scan the table, and record the minimum price in the range [0, i – 1], so the potential max profit is prices[i] – min(prices[0, i-1])

The following is the implementation in Java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public class BestTimetoBuyandSellStock { public int maxProfit(int[] prices) { if (prices.length == 0) { return 0; } int maxProfit = 0; int minPrice = prices[0]; for (int i = 1; i < prices.length; i++) { maxProfit = Math.max(maxProfit, prices[i] - minPrice); minPrice = Math.min(minPrice, prices[i]); } return maxProfit; } } } |

[Read More...]