Say you have an array for which the ith 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: 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: Input: [7, 6, 4, 3, 1] Output: 0

In this case, no transaction is done, i.e. max profit = 0.

s思路： 1. 低價買入，高價賣出！從左往右遍歷，當遇到開始增加的位置就是可能的低價位，然后遍歷后面的高價位，找最大的差值！ 2. 這道題有意思的地方在于：lowprice是目前為止的最小值，后面遇到的值和這個最小值的差值即為目前位置的最大值，兩個變量就可以模擬這個動態的過程：lowprice為目前最小值，profit為目前最大profit:而profit=max(profit,prices[i]-lowprice).