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.
分析
找出一段最大值和最小值之差。使用贪心法，如果碰到一个更大的，计算当前利润，如果更大保存在结果中，如果碰到更小的，就以该小值重新初始化最大和最小值，然后向后计算。
还有一种Kadane's Algorithm，一直递加前个元素和后个元素之差，如果小于0，赋值0，然后找到这个过程中最大的值即可。
int maxProfit(int* prices, int pricesSize) {
if(pricesSize==0||pricesSize==1)return 0;
int min=prices[0],max=prices[0],profit=0;
for(int i=1;i<pricesSize;i++)
{
if(prices[i]>max)
max=prices[i];
if(prices[i]<min)
{
min=prices[i];
max=prices[i];
}
if(max-min>profit)
profit=max-min;
}
return profit;
}
