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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 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
Explanation: In this case, no transaction is done, i.e. max profit = 0.
遍歷一遍堤如，期間維護(hù)兩個值盼樟，一個是當(dāng)前最大值辛块，一個是遍歷過的數(shù)字中的最小值酬土，則最新的最大值會產(chǎn)生在當(dāng)前最大值與（當(dāng)前數(shù)字減去最小值）之間竹握，不斷更新。
public class Solution {
public int MaxProfit(int[] prices) {
int result = 0;
int min = (prices.Length>0) ? prices[0] : 0 ; //記錄遍歷過的最小值
for (int i = 0; i < prices.Length; ++i) {
min = Math.Min(min, prices[i]);
result = Math.Max(result, prices[i]-min); //對比當(dāng)前最大值 vs 新增可能最大值
}
return result;
}
}
