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.
分析
找出一段最大值和最小值之差。使用貪心法壁榕，如果碰到一個(gè)更大的萌丈，計(jì)算當(dāng)前利潤，如果更大保存在結(jié)果中揍很，如果碰到更小的郎楼，就以該小值重新初始化最大和最小值万伤，然后向后計(jì)算。
還有一種Kadane's Algorithm呜袁，一直遞加前個(gè)元素和后個(gè)元素之差敌买，如果小于0，賦值0阶界，然后找到這個(gè)過程中最大的值即可虹钮。
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;
}
