The Question

Best Time to Buy and Sell Stock IV

You are given an integer array prices where prices[i] is the price of a given stock on the $i^{th}$ day, and an integer k representing the maximum number of transactions allowed. A single transaction consists of one purchase and one subsequent sale. You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). Return the maximum profit you can achieve with at most k transactions.

Java

Greedy

Questions & Insights

Clarifying Questions

What are the constraints on $N$ (number of days) and $k$? (Assumption:

N

up to 1000,

k

up to 1000. If

k \ge N/2

, we can perform as many transactions as we want.)

Can we buy and sell on the same day? (Assumption: Yes, but it results in 0 profit and consumes a transaction, so it is never optimal unless required to meet exactly

k

, though the problem says "at most

k

").

Are there any negative prices? (Assumption: Stock prices are non-negative integers).

What is the expected time and space complexity? (Assumption:

O(nk)

time and

O(k)

O(nk)

space).

Thinking Process

State Definition: We need to track two things: the number of transactions completed and whether we currently hold a stock. Let buy[j] be the max profit after

j

transactions ending in a "buy" state, and sell[j] be the max profit after

j

transactions ending in a "sell" state.

Base Case/Optimization: If

k

is very large (specifically

k \ge N/2

), the constraint becomes irrelevant because we can't physically perform more than

N/2

profitable transactions (each requires a buy day and a separate sell day). In this case, we use a simple greedy approach to sum all positive price differences.

Transitions:

For each day

i

and each transaction

j \in [1, k]

buy[j] = max(buy[j], sell[j-1] - prices[i]) (Either stay in previous buy state or buy today using profit from previous sell).

sell[j] = max(sell[j], buy[j] + prices[i]) (Either stay in previous sell state or sell today based on current buy state).

Memory Efficiency: Instead of a full 2D DP table dp[k][n], we can maintain two arrays of size

k+1

to represent the states, as day

i

only depends on day

i-1

Implementation Breakdown

Problem Set

Functional Requirements: Calculate maximum profit with at most

k

buy-sell pairs.

Constraints:

1 \le prices.length \le 1000

0 \le k \le 1000

Must sell before buying again.

Approach

Algorithm: Dynamic Programming (with Greedy optimization for large

k

Data Structure: 1D Arrays (State Compression).

Complexity:

Time:

O(n \cdot k)

normally,

O(n)

k \ge n/2

Space:

O(k)

to store the states.

Implementation

Wrap Up

Advanced Topics

WQS Binary Search (Aliens Trick): For very large

N

and

k

where

O(NK)

is too slow, this problem can be solved in

O(N \log (\max(prices)))

using a technique that binary searches on a "transaction fee" to hit exactly

k

transactions.

Space Optimization: We used

O(k)

space. This is generally the lower bound for this DP approach, though for specific constraints, we could use bit-packing or short integers if price values are small.

Parallelization: While DP is inherently sequential across days, we can parallelize the updates across the k transactions for each day, though the overhead usually exceeds the gain for

k=1000