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

---

Timeline

timeline

2025-10-01

init

dynamic programming

---

Title:

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, 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 yesterday and didn’t buy today, or we held yesterday and sold today (here we directly add prices[i] because when buying stock we directly subtract prices[i]; we can understand 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 yesterday and didn’t buy today, or we held yesterday and bought today (here we directly subtract prices[i] because when buying stock we directly add prices[i]; we can understand 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] maximum profit on day i without holding stock
    // dp[i][1] 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;
  }
};