面试经典150题 P122 买卖股票的最佳时机 II

---

时间轴

时间轴

2025-10-01

init

动态规划

---

题目：

P122 买卖股票的最佳时机 II

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/?envType=study-plan-v2&envId=top-interview-150

假设 dp[i][0]表示第 i 天的最大利润且不持有股票,dp[i][1]表示第 i 天最大利润且持有股票那么:

$$dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])$$

第 i 天不持有股票可能是昨天就不持有,今天也不买入,也有可能是昨天持有,今天卖出(这里直接+prices[i]是因为买入股票时我们直接-prices[i],可以理解为我们维护的是当前的余额)

$$dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])$$

第 i 天持有股票可能是昨天就持有,今天也不买入,也有可能是昨天持有,今天买入(这里直接-prices[i]是因为买入股票时我们直接+prices[i],可以理解为我们维护的是当前的余额)

#include <algorithm>
#include <climits>
#include <utility>
#include <vector>

using std::pair;
using std::vector;

class Solution {
public:
  int maxProfit(vector<int> &prices) {
    // dp[i][0] 第i天最大利润并且不持有股票
    // dp[i][1] 第i天最大利润且持有股票
    int n;
    n = prices.size();
    vector<pair<int, int>> dp(n, {0, 0});
    // dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
    // dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])
    dp[0].first = 0;
    dp[0].second = -prices[0];

    for (int i = 1; i < n; i++) {
      dp[i].first = std::max(dp[i - 1].first, dp[i - 1].second + prices[i]);
      dp[i].second = std::max(dp[i - 1].first - prices[i], dp[i - 1].second);
    }
    return dp[n - 1].first;
  }
};