题解 | #买卖股票的最好时机#

这个题目我一开始的想法是，找数组中的最大值，记录该最大值的下标，然后在该下标之前的数据中找最小值，最大值与最小值的差值，就是获得的最大收益，返回这个差值即可。
但是这个想法存在以下问题：
（1）最大值出现在第0天，之后递减，例如[4,2,1]
（2）最大值出现在第0天，之后有次大值，在最大值和次大值之间有最小值，例如[4,1,2]
仅仅是靠上述想法，是不能在这两种情况下正确输出结果的。于是在看了其他人的题解、讨论之后，我发现我还存在一定的理解误区：只有买入了股票才能卖出,这句话我一开始理解的是如果以第i天的价格卖出，那么就要以第i-1天以及之前的价格买，但是显然还有一种情况那就是当天买当天卖，这种情况就比较适用于解决上面提到的问题(1)。但是对于问题(2),还是没有解决，所以可以看到我之前的想法有问题。
于是可以这样考虑，只要在当天之前，以最便宜的价格买入即可。但是这个挑选最便宜的过程，不是像之前一样寻找，而是从第0天开始，假定该价格为买入的价格，然后每次以该价格与当天价格对比，哪个小就把哪个重新记为买入价格，并且计算当前价格与买入价格的差值(也就是收益)，并将收益和初始定义的收益比较取最大值，重新赋给收益变量，这样就可以保证该收益变量里的值永远都是卖出当天价格值减去当天之前最便宜买入价格的差值，也就是所求的最大收益。（注：将初始定义的收益定义成0，就可以保证问题(1)的错误不会发生）
代码如下

class Solution {
public:
    /**
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        int len = prices.size();
        int buy = prices[0];//表示第i天卖出时的买入价格
        int dp = 0;//表示收益
        for(int i = 0; i < len; i++)
        {
            buy = min(buy,prices[i]);
            dp=max(dp,prices[i]-buy);
        }
        return dp;
    }
};