LeetCode OJ - Best Time to Buy and Sell Stock

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 位置卖出时值须要知道过去的最低价minPrices就可以，在i位置得到最大收益。多次迭代求出在n-1位置得最大收益。

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