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:
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
 Example 2:
 Input:
Output: 0

In this case, no transaction is done, i.e. max profit = 0.
 最直接的方法，两层for循环比较两个数差值最大的组合，代码如下： 

int max(int a,int b)
{
    return (a>b)?a:b;
}
int maxProfit(int* prices, int pricesSize) 
{
    int curr = 0;
    for(int i = 0;i < pricesSize - 1;i++)
    {
        for(int j = i+1;j < pricesSize;j++)
        {
            if(prices[j] > prices[i])
                curr = max(curr,prices[j]-prices[i]);
        }
    }
    return curr;
}

执行结果：
另一种巧妙的方法如下： 

int max(int a,int b)
{
    return (a>b)?a:b;
}
int maxProfit(int* prices, int pricesSize) 
{
    int maxCur = 0, maxSoFar = 0;
    for(int i = 1; i < pricesSize; i++)
    {
        maxCur = max(0, maxCur += prices[i] - prices[i-1]);
        maxSoFar = max(maxCur, maxSoFar);
    }
    return maxSoFar;
}

执行结果：
 

int max(int a,int b)
{
    return (a>b)?a:b;
}

int min(int a,int b)
{
    return (a<b)?a:b;
}

int maxProfit(int* prices, int pricesSize) 
{
    if(NULL == prices || 0 == pricesSize)
        return 0;
    
    int low = prices[0];
    int result = 0;
    for(int i = 1;i < pricesSize;i++)
    {
        low = min(low,prices[i]);
        result = max(result,prices[i]-low);
    }
    return result;
}

最后一种方法是一直更新最小值，然后用当前值减去最小值去找出来两者差最大值。
 c++版本： 

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int size = prices.size();
        if(size <= 0)
            return 0;
        int minvalue = prices[0],res = 0;
        for(int i = 1;i < size;i++)
        {
            minvalue = min(minvalue,prices[i]);
            res = max(res,prices[i] - minvalue);
        }
        
        return res;
    }
};