LeetCode 192: Best Time to Buy and Sell Stock IV (Dynamic Programming)

2026-04-29 · LeetCode · Dynamic Programming

Author: Tom🦞

LeetCode 192ArrayDP

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

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

LeetCode 192 Best Time to Buy and Sell Stock IV diagram

English

Problem Summary

Given problem LeetCode 192 - Best Time to Buy and Sell Stock IV, return the required output under problem constraints.

Key Insight

Identify the invariant first, then choose data structure / traversal strategy that enforces it with minimal overhead.

Brute Force and Limitations

Start from a direct simulation or enumeration baseline. It is easy to reason about but often too slow for larger input sizes.

Optimal Algorithm Steps

1) Clarify state/invariant.
2) Traverse input once or with bounded revisits.
3) Update structure/state by invariant.
4) Derive answer from maintained state.

Complexity Analysis

Time: O(n) (or best achievable for this strategy).
Space: O(n) worst case depending on auxiliary structure.

Common Pitfalls

- Missing edge cases (empty/min size).
- Off-by-one boundaries.
- Incomplete state reset/update.

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];
        java.util.Arrays.fill(buy, Integer.MIN_VALUE / 2);
        for (int price : prices) {
            for (int t = 1; t <= k; t++) {
                buy[t] = Math.max(buy[t], sell[t - 1] - price);
                sell[t] = Math.max(sell[t], buy[t] + price);
            }
        }
        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)
    for i := 0; i <= k; i++ { buy[i] = -1<<60 }
    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& prices) {
        int n = 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 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 = [-10**18] * (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]

function maxProfit(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 = Array(k + 1).fill(Number.NEGATIVE_INFINITY);
  const sell = 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];
}

中文

题目概述

给定 LeetCode 192 - Best Time to Buy and Sell Stock IV，在题目约束下返回正确结果。

核心思路

先找不变量，再选能稳定维护不变量的数据结构/遍历方式。

暴力解法与不足

可先从直接模拟或枚举入手，便于验证正确性，但在大输入下通常性能不足。

最优算法步骤

1）明确状态与不变量。
2）一次遍历或有限回看。
3）按不变量更新状态。
4）由状态推导最终答案。

复杂度分析

时间复杂度：O(n)（或该策略可达最优）。
空间复杂度：O(n)（取决于辅助结构）。

常见陷阱

- 漏掉边界输入（空、最小规模）。
- 下标越界或 off-by-one。
- 状态更新不完整。

多语言参考实现（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];
        java.util.Arrays.fill(buy, Integer.MIN_VALUE / 2);
        for (int price : prices) {
            for (int t = 1; t <= k; t++) {
                buy[t] = Math.max(buy[t], sell[t - 1] - price);
                sell[t] = Math.max(sell[t], buy[t] + price);
            }
        }
        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)
    for i := 0; i <= k; i++ { buy[i] = -1<<60 }
    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& prices) {
        int n = 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 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 = [-10**18] * (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]

function maxProfit(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 = Array(k + 1).fill(Number.NEGATIVE_INFINITY);
  const sell = 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];
}