学步园

Say you have an array for which the i^th 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.

基本题，注意不能直接找最大跟最小的那天然后求差，因为价高的时间可能在前面，而时间是向前的。

简单来说就是：假如我们在第i天买入，那么卖出应该在i天之后的价值最高的那天，也就规约为求每个i右边的最高的那个值与自己的差值就是了。

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if ( prices.empty())
            return 0;
        int n=prices.size();
        int high=prices[n-1];
        int ans=0;
        for(int i=n-1;i>=0;i--)
        {
            high=max(high,prices[i]);
            ans=max(ans,high-prices[i]);
        }
        return ans;
    }
};