[LeetCode]Best Time to Buy and Sell Stock

/**********************************************************************************
* 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.
**********************************************************************************/

假定有一个数组，第i个元素代表第i天的股票价格。在只允许一次买卖交易的条件下，能够得到的最大收益是多少？

动态规划的算法思路：买入点初始定为第一个元素，遇到比买入点更低的点则更新买入点，遇到使利润更大的卖出点则更新利润。由于max一直保持着当前的最大利润，所以不用担心更新买入点后卖不出前面那么好的价钱。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
    int low = 0;
    int max = 0;    //因为可以选择不买，所以利润至少为0
    for(int i=0;i<prices.size();i++)
    {
        //找到一个比当前最低点还要低的点，可直接替换
        //可以替换的理由是：前面i-1个点中买卖能得到的最大利润已经keep了
        //对于后面的最高点，该点亦是前面最低的买入价格
        if(prices[i]-prices[low]<=0)
        {
            low = i;
        }
        //如果当前点卖出得到的利润更大，更新max值
        if(prices[i]-prices[low]>max)
        {
            max = prices[i] - prices[low];
        }
    }
    return max;
    }
};