---
title: 'Best Time to Buy and Sell Series'
author: Jay Chen
tags: LeetCode
---

# Best Time to Buy and Sell Series

## Notation

- `prices`: stock price array
- `k`: max #transactions allowed to complete
- `dp[i][k][j]`: the max profix that could be gained
- at the end of `i`th day
- w/ at most `k` transactions and
- w/ `j` stocks in hand
AFTER taking the action

## Base case

- `dp[-1][k][0] = 0` (`i = -1` means no stock)
- `dp[i][0][0] = 0` (no transaction)
- `dp[-1][k][1] = -Inf` (no stock but `1` in hand is impossible)
- `dp[i][0][1] = -Inf` (no transaction but `1` in hand is impossible)

## Recurrence relations

- `dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])`, rest or sell
- `dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])`, rest or buy (note that `k - 1` because buying `prices[i]` cost one transaction)

## Case I: `k = 1`

[121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)

- `dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])`
- `dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])`
- `dp[i][1][1] = max(dp[i - 1][1][1], -prices[i])`, where `dp[i - 1][0][0] = 0` (no transaction)

class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    int sellOne = 0;
    int holdOne = INT_MIN;

    for (const int price : prices) {
      sellOne = max(sellOne, holdOne + price);
      holdOne = max(holdOne, -price);
    }

    return sellOne;
  }
};

## Case II: `k = +Infinity`

[122. Best Time to Buy and Sell Stock II](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/)

When $k \to \infty$, there's no difference between `k` and `k - 1`.

- `dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])`
- `dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])`
- `dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i])`, where `dp[i - 1][k - 1][0] = T[i - 1][k][0]`

class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    int sell = 0;
    int hold = INT_MIN;

    for (const int price : prices) {
      sell = max(sell, hold + price);
      hold = max(hold, sell - price);
    }

    return sell;
  }
};

## Case III: `k = 2`

[123. Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/)

- `dp[i][2][0] = max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i])`
- `dp[i][2][1] = max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i])`
- `dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])`
- `dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])`
- `dp[i][1][1] = max(dp[i - 1][1][1], -prices[i])`, where `dp[i - 1][0][0] = 0` (no transaction)

class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    int sellTwo = 0;
    int holdTwo = INT_MIN;
    int sellOne = 0;
    int holdOne = INT_MIN;

    for (const int price : prices) {
      sellTwo = max(sellTwo, holdTwo + price);
      holdTwo = max(holdTwo, sellOne - price);
      sellOne = max(sellOne, holdOne + price);
      holdOne = max(holdOne, -price);
    }

    return sellTwo;
  }
};

## Case IV: `k = arbitrary`

[188. Best Time to Buy and Sell Stock IV](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/)

- `dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])`
- `dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])`
- `dp[i][1][1] = max(dp[i - 1][1][1], -prices[i])`, where `dp[i - 1][0][0] = 0` (no transaction)

class Solution {
 public:
  int maxProfit(int k, vector<int>& prices) {
    // reduce the problem to `k == +Infinity`
    if (k >= prices.size() / 2) {
      int sell = 0;
      int hold = INT_MIN;

      for (const int price : prices) {
        sell = max(sell, hold + price);
        hold = max(hold, sell - price);
      }

      return sell;
    }

    vector<int> sell(k + 1);
    vector<int> hold(k + 1, INT_MIN);

    for (int price : prices)
      for (int i = k; i > 0; i--) {
        sell[i] = max(sell[i], hold[i] + price);
        hold[i] = max(hold[i], sell[i - 1] - price);
      }

    return sell[k];
  }
};

## Case V: `k = +Infinity` with cooldown

[309. Best Time to Buy and Sell Stock with Cooldown](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/)

- `dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])`
- `dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 2][k][0] - prices[i])`

class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    int sell = 0;
    int hold = INT_MIN;
    int prev = 0;

    for (const int price : prices) {
      const int cache = sell;
      sell = max(sell, hold + price);
      hold = max(hold, prev - price);
      prev = cache;
    }

    return sell;
  }
};

| index | | 0 | 1 | 2 | 3 | 4 |
| :----: | :-------: | :-: | :---------: | :---------: | :---------------------------------: | :---------: |
| prices | | 1 | 2 | 3 | 0 | 2 |
| sell | 0 | 0 | -1 + 2 = 1 | -1 + 3 = 2 | 2 | 1 + 2 = 3 |
| hold | $-\infty$ | -1 | -1 | -1 | **1 - 0 = 1** (sell[1] - prices[3]) | 1 |
| prev | 0 | 0 | 0 = sell[0] | 1 = sell[1] | 2 = sell[2] | 2 = sell[3] |

## Case VI: `k = +Infinity` with fee

[714. Best Time to Buy and Sell Stock with Transaction Fee](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)

**We can charge the fee when buying or selling.**

- `dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])`
- `dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i] - fee)`

or

- `dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i] - fee)`
- `dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i])`

class Solution {
 public:
  int maxProfit(vector<int>& prices, int fee) {
    int sell = 0;
    int hold = INT_MIN;

    for (const int price : prices) {
      sell = max(sell, hold + price);
      hold = max(hold, sell - price - fee);
    }

    return sell;
  }
};