LeetCode 3573 - Best Time to Buy and Sell Stock V

This problem extends the classic stock trading dynamic programming family by allowing two different kinds of transactions. A normal transaction consists of buying first and selling later. If the stock price rises, the profit is: A short selling transaction reverses the order.

leetcodemediumarraydynamic-programming

LeetCode Problem 3573

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

LeetCode 3573 - Best Time to Buy and Sell Stock V

Problem Understanding

This problem extends the classic stock trading dynamic programming family by allowing two different kinds of transactions.

A normal transaction consists of buying first and selling later. If the stock price rises, the profit is:

$$\text{sell price} - \text{buy price}$$

A short selling transaction reverses the order. We sell first and buy back later. If the stock price falls, the profit is:

$$\text{sell price} - \text{buy back price}$$

We are given an array prices, where prices[i] represents the stock price on day i, and an integer k representing the maximum number of transactions we may perform.

The important constraints are:

  • Transactions cannot overlap.
  • A transaction must be completely closed before another one starts.
  • If we close a transaction on day i, we cannot immediately open another transaction on the same day.
  • We may perform at most k transactions.
  • We may choose fewer than k transactions if doing so is optimal.

The goal is to maximize total profit.

The array length is at most 1000, while k ≤ n/2. This immediately suggests that exponential exploration of all transaction choices is impossible. We need a dynamic programming solution.

Several edge cases are important:

  • Prices may be strictly increasing, making only normal transactions useful.
  • Prices may be strictly decreasing, making only short transactions useful.
  • Prices may oscillate, requiring a mixture of both transaction types.
  • Sometimes the best solution uses fewer than k transactions.
  • Equal prices can occur, creating zero-profit opportunities that should generally be ignored.

Approaches

Brute Force

A brute force solution would recursively try every possible action on every day.

For each day we could:

  • Do nothing.
  • Open a normal position.
  • Open a short position.
  • Close an existing position.

The recursion would track:

  • Current day.
  • Number of completed transactions.
  • Whether we currently hold a long position.
  • Whether we currently hold a short position.

Since each day branches into multiple possibilities, the number of states explored grows exponentially. Even with memoization, the state space becomes extremely large if positions are tracked naively.

This approach is correct because it explicitly explores every valid sequence of transactions, but it is far too slow for n = 1000.

Optimal Dynamic Programming

The key observation is that this problem is essentially the classic "at most k transactions" stock DP, except that a transaction may be either:

  • Long (buy then sell)
  • Short (sell then buy)

For each transaction count t, we only need to know three possible states:

  • No active position.
  • Currently holding a long position.
  • Currently holding a short position.

Let:

  • flat[t] = maximum profit after completing exactly t transactions and currently having no open position.
  • long[t] = maximum profit after completing t transactions and currently holding a long position.
  • short[t] = maximum profit after completing t transactions and currently holding a short position.

When processing a new day:

  • We may open a long position from flat.
  • We may open a short position from flat.
  • We may close a long position into flat.
  • We may close a short position into flat.

This gives an O(nk) solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Explores every valid transaction sequence
Optimal DP O(nk) O(k) Tracks flat, long, and short states

Algorithm Walkthrough

Step 1

Create three arrays of length k + 1.

  • flat[t]
  • long[t]
  • short[t]

Initialize:

  • flat[0] = 0
  • Everything else = negative infinity

This means we start with zero profit, no position, and no completed transactions.

Step 2

Process prices one day at a time.

For each price, create copies of the current DP arrays. This prevents opening and closing a transaction on the same day.

Step 3

Attempt to open new positions.

For every transaction count t:

  • Open a long position:

$$long[t] = \max(long[t], flat[t] - price)$$

  • Open a short position:

$$short[t] = \max(short[t], flat[t] + price)$$

The long state subtracts the purchase cost.

The short state adds the proceeds from the short sale.

Step 4

Attempt to close existing long positions.

If a long position exists:

$$flat[t+1] = \max(flat[t+1], long[t] + price)$$

Selling completes one transaction.

Step 5

Attempt to close existing short positions.

If a short position exists:

$$flat[t+1] = \max(flat[t+1], short[t] - price)$$

Buying back completes one transaction.

Step 6

Replace the old arrays with the newly computed arrays.

This ensures all transitions respect the rule that opening and closing cannot occur on the same day.

Step 7

After processing all days, return the largest value among all flat[t].

Only fully closed transactions count toward the answer.

Why it works

The invariant is that after processing day i, each DP state stores the maximum achievable profit among all valid transaction sequences ending in that exact state.

Every legal action corresponds to exactly one DP transition:

  • Opening a long position.
  • Opening a short position.
  • Closing a long position.
  • Closing a short position.
  • Doing nothing.

Since all possible legal actions are represented and every state keeps only the best profit achievable, the DP explores every valid strategy while discarding inferior ones. Therefore the final maximum flat[t] is the optimal answer.

Python Solution

from typing import List

class Solution:
    def maximumProfit(self, prices: List[int], k: int) -> int:
        NEG_INF = float("-inf")

        flat = [NEG_INF] * (k + 1)
        long = [NEG_INF] * (k + 1)
        short = [NEG_INF] * (k + 1)

        flat[0] = 0

        for price in prices:
            next_flat = flat[:]
            next_long = long[:]
            next_short = short[:]

            for t in range(k + 1):
                if flat[t] != NEG_INF:
                    next_long[t] = max(next_long[t], flat[t] - price)
                    next_short[t] = max(next_short[t], flat[t] + price)

            for t in range(k):
                if long[t] != NEG_INF:
                    next_flat[t + 1] = max(
                        next_flat[t + 1],
                        long[t] + price
                    )

                if short[t] != NEG_INF:
                    next_flat[t + 1] = max(
                        next_flat[t + 1],
                        short[t] - price
                    )

            flat = next_flat
            long = next_long
            short = next_short

        return int(max(flat))

The implementation directly follows the state definition.

The flat array stores profits when no position is active. The long array stores profits while holding a traditional long position. The short array stores profits while holding a short position.

For every price, new arrays are created so that all transitions use states from the previous day. This enforces the requirement that a transaction cannot be opened and closed on the same day.

Opening a long subtracts the current price. Opening a short adds the current price. Closing either type increases the completed transaction count by one.

The final answer is the maximum profit among all flat states because only closed transactions contribute to realized profit.

Go Solution

func maximumProfit(prices []int, k int) int64 {
	const NEG int64 = -(1 << 60)

	flat := make([]int64, k+1)
	longPos := make([]int64, k+1)
	shortPos := make([]int64, k+1)

	for i := 0; i <= k; i++ {
		flat[i] = NEG
		longPos[i] = NEG
		shortPos[i] = NEG
	}

	flat[0] = 0

	for _, p := range prices {
		price := int64(p)

		nextFlat := append([]int64(nil), flat...)
		nextLong := append([]int64(nil), longPos...)
		nextShort := append([]int64(nil), shortPos...)

		for t := 0; t <= k; t++ {
			if flat[t] != NEG {
				if flat[t]-price > nextLong[t] {
					nextLong[t] = flat[t] - price
				}

				if flat[t]+price > nextShort[t] {
					nextShort[t] = flat[t] + price
				}
			}
		}

		for t := 0; t < k; t++ {
			if longPos[t] != NEG {
				candidate := longPos[t] + price
				if candidate > nextFlat[t+1] {
					nextFlat[t+1] = candidate
				}
			}

			if shortPos[t] != NEG {
				candidate := shortPos[t] - price
				if candidate > nextFlat[t+1] {
					nextFlat[t+1] = candidate
				}
			}
		}

		flat = nextFlat
		longPos = nextLong
		shortPos = nextShort
	}

	ans := int64(0)

	for _, value := range flat {
		if value > ans {
			ans = value
		}
	}

	return ans
}

The Go version mirrors the Python implementation. The primary difference is the use of int64 throughout the DP because prices can be as large as 10^9, and multiple profitable transactions can accumulate beyond the safe range of a 32-bit integer. Slices are copied each day using append([]int64(nil), ...) so that transitions always use states from the previous day.

Worked Examples

Example 1

Input:

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

Initial state:

t flat long short
0 0 -∞ -∞
1 -∞ -∞ -∞
2 -∞ -∞ -∞

After day 0, price = 1:

t flat long short
0 0 -1 1
1 -∞ -∞ -∞
2 -∞ -∞ -∞

After day 2, price = 9:

Closing the long position opened at price 1 yields:

profit = 9 - 1 = 8

State includes:

t flat
1 8

After day 3, price = 8:

Open a short position from flat[1]=8.

short[1] = 8 + 8 = 16

After day 4, price = 2:

Close short:

profit = 16 - 2 = 14

Final answer:

14

Example 2

Input:

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

Optimal transactions:

Transaction Profit
Buy 12, sell 19 7
Short 19, cover 8 11
Buy 1, sell 19 18

Total:

7 + 11 + 18 = 36

The DP discovers these profits through successive transitions:

Completed Transactions Best Flat Profit
0 0
1 7
2 18
3 36

Final answer:

36

Complexity Analysis

Measure Complexity Explanation
Time O(nk) Each day processes all transaction counts
Space O(k) Three DP arrays of size k + 1

For every one of the n days, we iterate through all k + 1 transaction counts and perform a constant number of state transitions. The memory usage remains linear in k because only the previous day's DP states are needed.

Test Cases

sol = Solution()

assert sol.maximumProfit([1,7,9,8,2], 2) == 14  # example 1

assert sol.maximumProfit(
    [12,16,19,19,8,1,19,13,9], 3
) == 36  # example 2

assert sol.maximumProfit([1,2], 1) == 1  # single increasing move

assert sol.maximumProfit([2,1], 1) == 1  # single decreasing move via short

assert sol.maximumProfit([5,5], 1) == 0  # no profit possible

assert sol.maximumProfit([1,2,3,4,5], 2) == 4  # pure long strategy

assert sol.maximumProfit([5,4,3,2,1], 2) == 4  # pure short strategy

assert sol.maximumProfit([1,10,1,10], 2) == 18  # two profitable longs

assert sol.maximumProfit([10,1,10,1], 2) == 18  # two profitable shorts

assert sol.maximumProfit([3,8,2,9], 2) == 12  # mixed opportunities

assert sol.maximumProfit([7,7,7,7], 2) == 0  # all equal prices

assert sol.maximumProfit([1,1000,1,1000,1], 2) == 1998  # large profits

assert sol.maximumProfit([1000,1,1000,1,1000], 2) == 1998  # alternating extremes

Test Summary

Test Why
[1,7,9,8,2], k=2 Official example 1
[12,16,19,19,8,1,19,13,9], k=3 Official example 2
[1,2], k=1 Smallest increasing case
[2,1], k=1 Smallest decreasing case
[5,5], k=1 Zero-profit scenario
[1,2,3,4,5], k=2 Monotonic increase
[5,4,3,2,1], k=2 Monotonic decrease
[1,10,1,10], k=2 Multiple long trades
[10,1,10,1], k=2 Multiple short trades
[3,8,2,9], k=2 Mix of rising and falling segments
[7,7,7,7], k=2 Constant prices
[1,1000,1,1000,1], k=2 Large positive gains
[1000,1,1000,1,1000], k=2 Alternating peaks and valleys

Edge Cases

Strictly Increasing Prices

When prices continuously rise, short selling never helps. A buggy implementation might still open and close unnecessary short positions. The DP naturally avoids this because such transitions never improve profit, so the optimal solution becomes a sequence of long transactions only.

Strictly Decreasing Prices

This is the mirror image of the classic stock problem. Traditional solutions that only support buying before selling would fail here. Because the DP explicitly tracks short positions, it can profit from every downward movement and return the correct maximum value.

Equal Consecutive Prices

When prices remain unchanged across multiple days, opening and closing a transaction yields zero profit. Such cases can expose bugs related to transaction counting or state transitions. The implementation handles them correctly because zero-profit transitions compete normally in the maximization process and never force unnecessary transactions.

Using Fewer Than k Transactions

The problem allows at most k transactions, not exactly k. Sometimes the optimal strategy stops early because additional transactions cannot increase profit. By taking the maximum over all flat[t], where 0 ≤ t ≤ k, the algorithm correctly returns the best achievable profit regardless of how many transactions are actually used.

Transaction Boundary Restrictions

A subtle rule states that after closing a transaction on a day, another transaction cannot be opened on that same day. The solution enforces this by creating fresh DP arrays for each day and performing all transitions from the previous day's states. Consequently, a transaction cannot be both closed and reopened on the same date.