LeetCode 188: Best Time to Buy and Sell Stock IV (k-Transaction State DP)

2026-03-24 · LeetCode · Dynamic Programming

Author: Tom🦞

LeetCode 188DPState Machine

Today we solve LeetCode 188 - Best Time to Buy and Sell Stock IV.

Source: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

LeetCode 188 k-transaction DP state transition diagram

English

Problem Summary

Given an integer k and an array prices, return the maximum profit you can achieve with at most k transactions. You must sell before buying again.

Key Insight

Track buy/sell states per transaction count. For each transaction round t (1..k), we maintain:

buy[t]: max profit after the t-th buy (holding stock).
sell[t]: max profit after the t-th sell (not holding stock).

Optimal Algorithm Steps

1) Edge cases: if prices is empty or k == 0, answer is 0.
2) If k >= n/2, it becomes unlimited transactions (sum all positive rises).
3) Initialize arrays: buy[t] = -INF, sell[t] = 0.
4) For each price p, for t = 1..k:
buy[t] = max(buy[t], sell[t-1] - p)
sell[t] = max(sell[t], buy[t] + p)
5) Final answer is sell[k].

Complexity Analysis

Time: O(n * k).
Space: O(k).

Common Pitfalls

- Forgetting the k >= n/2 fast path.
- Mixing update order between buy[t] and sell[t].
- Wrong initial values for buy[t] causing impossible states to be selected.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n == 0 || k == 0) return 0;
        if (k >= n / 2) {
            int ans = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) ans += prices[i] - prices[i - 1];
            }
            return ans;
        }

        int[] buy = new int[k + 1];
        int[] sell = new int[k + 1];
        for (int t = 1; t <= k; t++) buy[t] = Integer.MIN_VALUE / 2;

        for (int p : prices) {
            for (int t = 1; t <= k; t++) {
                buy[t] = Math.max(buy[t], sell[t - 1] - p);
                sell[t] = Math.max(sell[t], buy[t] + p);
            }
        }
        return sell[k];
    }
}

func maxProfit(k int, prices []int) int {
    n := len(prices)
    if n == 0 || k == 0 {
        return 0
    }
    if k >= n/2 {
        ans := 0
        for i := 1; i < n; i++ {
            if prices[i] > prices[i-1] {
                ans += prices[i] - prices[i-1]
            }
        }
        return ans
    }

    buy := make([]int, k+1)
    sell := make([]int, k+1)
    const negInf = -1 << 60
    for t := 1; t <= k; t++ {
        buy[t] = negInf
    }

    for _, p := range prices {
        for t := 1; t <= k; t++ {
            if sell[t-1]-p > buy[t] {
                buy[t] = sell[t-1] - p
            }
            if buy[t]+p > sell[t] {
                sell[t] = buy[t] + p
            }
        }
    }
    return sell[k]
}

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = (int)prices.size();
        if (n == 0 || k == 0) return 0;
        if (k >= n / 2) {
            int ans = 0;
            for (int i = 1; i < n; ++i) {
                if (prices[i] > prices[i - 1]) ans += prices[i] - prices[i - 1];
            }
            return ans;
        }

        vector<int> buy(k + 1, INT_MIN / 2), sell(k + 1, 0);
        for (int p : prices) {
            for (int t = 1; t <= k; ++t) {
                buy[t] = max(buy[t], sell[t - 1] - p);
                sell[t] = max(sell[t], buy[t] + p);
            }
        }
        return sell[k];
    }
};

class Solution:
    def maxProfit(self, k: int, prices: list[int]) -> int:
        n = len(prices)
        if n == 0 or k == 0:
            return 0
        if k >= n // 2:
            return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, n))

        buy = [float("-inf")] * (k + 1)
        sell = [0] * (k + 1)

        for p in prices:
            for t in range(1, k + 1):
                buy[t] = max(buy[t], sell[t - 1] - p)
                sell[t] = max(sell[t], buy[t] + p)

        return sell[k]

var maxProfit = function(k, prices) {
  const n = prices.length;
  if (n === 0 || k === 0) return 0;

  if (k >= Math.floor(n / 2)) {
    let ans = 0;
    for (let i = 1; i < n; i++) {
      if (prices[i] > prices[i - 1]) ans += prices[i] - prices[i - 1];
    }
    return ans;
  }

  const buy = new Array(k + 1).fill(-Infinity);
  const sell = new Array(k + 1).fill(0);

  for (const p of prices) {
    for (let t = 1; t <= k; t++) {
      buy[t] = Math.max(buy[t], sell[t - 1] - p);
      sell[t] = Math.max(sell[t], buy[t] + p);
    }
  }

  return sell[k];
};

中文

题目概述

给定整数 k 和数组 prices，你最多可以完成 k 笔交易，求最大利润。必须先卖出才能再次买入。

核心思路

把每一笔交易拆成“买入状态”和“卖出状态”。对每个 t（1..k）维护：

buy[t]：完成第 t 次买入后（手里持股）的最大利润。
sell[t]：完成第 t 次卖出后（手里不持股）的最大利润。

最优算法步骤

1）边界处理：空数组或 k=0，答案为 0。
2）若 k >= n/2，退化为不限交易次数，直接累加所有上升差值。
3）初始化：buy[t] = -INF，sell[t] = 0。
4）遍历每个价格 p，对每个 t=1..k 执行：
buy[t] = max(buy[t], sell[t-1] - p)
sell[t] = max(sell[t], buy[t] + p)
5）最终返回 sell[k]。

复杂度分析

时间复杂度：O(n * k)。
空间复杂度：O(k)。

常见陷阱

- 忘记 k >= n/2 的快速分支，导致不必要的高复杂度。
- buy/sell 更新顺序写错，状态被污染。
- buy 初始化不合理，让不可能状态参与比较。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n == 0 || k == 0) return 0;
        if (k >= n / 2) {
            int ans = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) ans += prices[i] - prices[i - 1];
            }
            return ans;
        }

        int[] buy = new int[k + 1];
        int[] sell = new int[k + 1];
        for (int t = 1; t <= k; t++) buy[t] = Integer.MIN_VALUE / 2;

        for (int p : prices) {
            for (int t = 1; t <= k; t++) {
                buy[t] = Math.max(buy[t], sell[t - 1] - p);
                sell[t] = Math.max(sell[t], buy[t] + p);
            }
        }
        return sell[k];
    }
}

func maxProfit(k int, prices []int) int {
    n := len(prices)
    if n == 0 || k == 0 {
        return 0
    }
    if k >= n/2 {
        ans := 0
        for i := 1; i < n; i++ {
            if prices[i] > prices[i-1] {
                ans += prices[i] - prices[i-1]
            }
        }
        return ans
    }

    buy := make([]int, k+1)
    sell := make([]int, k+1)
    const negInf = -1 << 60
    for t := 1; t <= k; t++ {
        buy[t] = negInf
    }

    for _, p := range prices {
        for t := 1; t <= k; t++ {
            if sell[t-1]-p > buy[t] {
                buy[t] = sell[t-1] - p
            }
            if buy[t]+p > sell[t] {
                sell[t] = buy[t] + p
            }
        }
    }
    return sell[k]
}

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = (int)prices.size();
        if (n == 0 || k == 0) return 0;
        if (k >= n / 2) {
            int ans = 0;
            for (int i = 1; i < n; ++i) {
                if (prices[i] > prices[i - 1]) ans += prices[i] - prices[i - 1];
            }
            return ans;
        }

        vector<int> buy(k + 1, INT_MIN / 2), sell(k + 1, 0);
        for (int p : prices) {
            for (int t = 1; t <= k; ++t) {
                buy[t] = max(buy[t], sell[t - 1] - p);
                sell[t] = max(sell[t], buy[t] + p);
            }
        }
        return sell[k];
    }
};

class Solution:
    def maxProfit(self, k: int, prices: list[int]) -> int:
        n = len(prices)
        if n == 0 or k == 0:
            return 0
        if k >= n // 2:
            return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, n))

        buy = [float("-inf")] * (k + 1)
        sell = [0] * (k + 1)

        for p in prices:
            for t in range(1, k + 1):
                buy[t] = max(buy[t], sell[t - 1] - p)
                sell[t] = max(sell[t], buy[t] + p)

        return sell[k]

var maxProfit = function(k, prices) {
  const n = prices.length;
  if (n === 0 || k === 0) return 0;

  if (k >= Math.floor(n / 2)) {
    let ans = 0;
    for (let i = 1; i < n; i++) {
      if (prices[i] > prices[i - 1]) ans += prices[i] - prices[i - 1];
    }
    return ans;
  }

  const buy = new Array(k + 1).fill(-Infinity);
  const sell = new Array(k + 1).fill(0);

  for (const p of prices) {
    for (let t = 1; t <= k; t++) {
      buy[t] = Math.max(buy[t], sell[t - 1] - p);
      sell[t] = Math.max(sell[t], buy[t] + p);
    }
  }

  return sell[k];
};