Interview Classic 150 Questions P122 Best Time to Buy and Sell Stock II

---

Timeline

Timeline

2025-10-01

init

Dynamic Programming

---

Problem:

P122 Best Time to Buy and Sell Stock II

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

Assume dp[i][0] represents the maximum profit on day i without holding stock, and dp[i][1] represents the maximum profit on day i while holding stock.
Then:

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

Not holding stock on day i could be because we didn’t hold it yesterday and don’t buy today, or because we held it yesterday and sell today (here we directly add prices[i] because when buying stock we directly subtract prices[i]; we can think of it as maintaining the current balance).

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

Holding stock on day i could be because we held it yesterday and don’t sell today, or because we didn’t hold it yesterday and buy today (here we directly subtract prices[i] because when buying stock we directly subtract prices[i]; we can think of it as maintaining the current balance).

#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] is the maximum profit on day i without holding stock
    // dp[i][1] is the maximum profit on day i while holding stock
    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;
  }
};