121. 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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

---

股票买卖问题。给定股票每天的价格，问哪天买入和哪天卖出能获得最大收益。动态规划问题，本科就遇到过了。之前一贯的做法是这样的：要使prices[j]-prices[i]的差值最大，因为prices[j]-prices[i]=(prices[j]-prices[j-1])+(prices[j-1]-prices[j-2])+…+(prices[i+1]-prices[i])，等式右边的每一项就是相邻两天的股价差。所以我们可以对每相邻两天的股价做差，得到一个新的n-1长的数组diff，然后对diff求最大连续子串和。最大连续子串和又可以用DP解决，令dp[i]为包含diff[i]的最大连续子串和，如果dp[i-1]>0，则dp[i]=dp[i-1]+diff[i]；否则dp[i]=diff[i]。最后dp数组的最大值即为最大收益。
这种思路的代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        if (prices.size() < 2)
            return 0;
        vector<int> diff(prices.size() – 1);
        for (int i = 1; i < prices.size(); ++i) {
            diff[i – 1] = prices[i] – prices[i – 1];
        }
        vector<int> dp(diff.size());
        int ans = 0;
        for (int i = 0; i < diff.size(); ++i) {
            if (i == 0 || dp[i – 1] < 0)
                dp[i] = diff[i];
            else
                dp[i] = dp[i – 1] + diff[i];
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

本代码提交AC，用时9MS。
还可以对上述思路简化，我们记录当前遇到的最小值min_so_far，那么如果第i天卖出的话，最大的收益就是prices[i]-min_so_far了，所以我们用dp[i]记录第i天卖出的最大收益。最后对dp数组求最大值，即为最大收益。
这种思路的代码如下：

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

本代码提交AC，用时6MS。
还有一种解法，用minprice和maxprice分别记录从左往右当前的最小值和从右往左当前的最大值，最大收益就是用maxprice-minprice的最大值。完整代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        int n = prices.size();
        if (n < 2)
            return 0;
        vector<int> minprice(n), maxprice(n);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            minprice[i] = (i == 0 ? prices[0] : min(minprice[i – 1], prices[i]));
            maxprice[n – i – 1] = (i == 0 ? prices[n – 1] : max(maxprice[n – i], prices[n – i – 1]));
        }
        for (int i = 0; i < n; ++i) {
            ans = max(ans, maxprice[i] – minprice[i]);
        }
        return ans;
    }
};

本代码提交AC，用时9MS。