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

方法一：贪心

遍历数组，创建两个int型变量分别用于维护最大的利润和更小的买入价格。

时间复杂度：o(n)

空间复杂度：o(1)

class Solution {
  public:
    int maxProfit(vector<int>& prices) {
        // 特殊情况处理
        if (prices.empty())
            return 0;
        // 记录最大利润
        int res = 0;
        // 记录更小的买入价格
        int min = prices[0];

        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] > min)
                res = max(res, prices[i] - min);
            else
                min = prices[i];
        }

        return res;
    }
};

方法二：动态规划

对于第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] = -prices[i - 1]；

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

时间复杂度：o(n)

空间复杂度：o(n)

class Solution {
  public:
    int maxProfit(vector<int>& prices) {
        // 特殊情况处理
        if (prices.empty())
            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], -1 * prices[i]);
        }

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