#3573

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Best Time to Buy and Sell Stock V

Maximize profit from stock trades with at most k transactions using state transition dynamic programming for precise decision-making.

array dynamic programming

Problem Statement

You are given an array prices where prices[i] represents the stock price on day i and an integer k representing the maximum allowed transactions. Each transaction consists of buying one share and selling one share, and you cannot start a new transaction before completing the previous one.

Determine the maximum total profit achievable by performing at most k transactions. Note that you cannot buy and sell on the same day within overlapping transactions, and you must carefully manage state transitions to avoid invalid sequences.

Examples

Example 1

Input: prices = [1,7,9,8,2], k = 2

Output: 14

Example 2

Input: prices = [12,16,19,19,8,1,19,13,9], k = 3

Output: 36

Constraints

2 <= prices.length <= 103
1 <= prices[i] <= 109
1 <= k <= prices.length / 2

Solution Approach

Dynamic Programming Table

Define a DP table dp[i][j] where i is the day and j is the number of completed transactions. Track the best profit for each state by considering whether to buy, sell, or skip on each day, respecting the transaction limit.

State Transitions

Use two states for each transaction count: hold and not-hold. Update hold[i][j] = max(hold[i-1][j], notHold[i-1][j-1] - prices[i]) and notHold[i][j] = max(notHold[i-1][j], hold[i-1][j] + prices[i]) to capture optimal decisions dynamically.

Optimization and Edge Cases

When k is larger than prices.length/2, treat it as unlimited transactions for faster O(n) solution. Handle single-day arrays, constant prices, and ensure DP table indexing avoids out-of-bound errors.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(k * n) using the DP table where n is the number of days and k is the transaction limit. Space complexity can be reduced from O(k * n) to O(k) by rolling arrays since each day depends only on the previous day states.

What Interviewers Usually Probe

Expect candidates to define buy and sell states clearly in DP.
Look for awareness of edge cases where k exceeds half of prices length.
Check for correct indexing and transaction completion constraints.

Common Pitfalls or Variants

Common pitfalls

Forgetting that you cannot buy and sell on the same day within overlapping transactions.
Mishandling cases where k is larger than half the number of days.
Using incorrect state transitions, leading to underestimated profits.

Follow-up variants

Unlimited transactions version reduces to simple peak-valley summation using O(n) scan.
Single transaction version simplifies to tracking minimum price and max profit in O(n).
Cooldown or transaction fee variations require modified DP states to include cooldown or cost.

FAQ

What pattern does Best Time to Buy and Sell Stock V use?

It uses state transition dynamic programming, tracking buy and sell states for each allowed transaction across days.

Can I use a greedy approach for this problem?

No, a greedy approach fails for k-limited transactions since local peaks do not guarantee global maximum profit.

How do I handle large k values efficiently?

When k >= prices.length/2, treat it as unlimited transactions and sum all positive differences between consecutive prices.

What is the time complexity of the DP solution?

The DP solution has O(k * n) time complexity and O(k) space if optimized with rolling arrays.

Can I buy and sell on the same day in this problem?

No, you cannot buy and sell on the same day within overlapping transactions; each transaction must complete before starting the next.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j][k]$ to represent the maximum profit on the first $i$ days, with at most $j$ transactions, and the current state $k$. Here, the state $k$ has three possibilities:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def maximumProfit(self, prices: List[int], k: int) -> int:
        n = len(prices)
        f = [[[0] * 3 for _ in range(k + 1)] for _ in range(n)]
        for j in range(1, k + 1):
            f[0][j][1] = -prices[0]
            f[0][j][2] = prices[0]
        for i in range(1, n):
            for j in range(1, k + 1):
                f[i][j][0] = max(
                    f[i - 1][j][0],
                    f[i - 1][j][1] + prices[i],
                    f[i - 1][j][2] - prices[i],
                )
                f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i])
                f[i][j][2] = max(f[i - 1][j][2], f[i - 1][j - 1][0] + prices[i])
        return f[n - 1][k][0]

Continue Practicing

#3575 maximum good subtree score #3578 count partitions with max min difference at most k #3562 maximum profit from trading stocks with discounts