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

方法一：动态规划

对于第i天可能有两种情况，持有股票和未持有股票。因此创建一个二维数组dp，用于存储第i天持有股票和未持有股票的最大利润。

可以得出以下的状态转移方程

（1）如果第i天未持有股票：

可能是因为此前从未买过股票或者之前已经卖出，这时dp[i][0] = dp[i - 1][0]；

可能是第i天才卖出，这是dp[i] = dp[i - 1][1] + prices[i - 1]；

所以dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])。

（2）如果第i天持有股票：

可能是因为之前购买的还未卖出，此时利润与前一天持有股票的利润一样，dp[i][1] = dp[i - 1][1]；

可能是因为之前已经卖出过，第i天才买入，dp[i][1] = dp[i - 1][0] - prices[i - 1]；

所以 dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])。

时间复杂度：o(n)

空间复杂度：o(n)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
	    // 特殊情况处理
        if (prices.size() == 1)
            return 0;
        
        vector<vector<int> >dp(prices.size(), vector<int> (2, 0));
	  	// 边界处理
        dp[0][0] = 0;
        dp[0][1] = -1 * prices[0];

        for (int i = 1; i < prices.size(); i++) {
		  	// 第i天没有持有股票的最大利润
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
		  	// 第i天持有股票的最大利润
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }

        return max(dp[prices.size() - 1][0], dp[prices.size() - 1][1]);
    }
};

方法二：贪心算法

时间复杂度：o(n)

空间复杂度：o(1)

class Solution {
  public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 1)
            return 0;

        int res = 0;
        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] > prices[i - 1])
                res += prices[i] - prices[i - 1];
        }
        return res;
    }
};