Stock buy and sell, including at most K transactions
Filed under Salesforce
Free read 3 of 3Ask whether the number of transactions is limited, whether you can hold only one share at a time and what to return if no profit is possible (0).
The question
Given an array of daily stock prices, find the maximum profit from buying and selling a stock, starting with a single transaction and extending up to at most K transactions. You must sell before buying again.
Constraints
- 0 <= K <= 100, 0 <= n <= 1000
- At most one share held at a time; no short selling
Examples
- Input
- k = 2, prices = [3,2,6,5,0,3]
- Output
- 7
- Why
- Buy at 2, sell at 6 (4) then buy at 0, sell at 3 (3).
Approach
Ask whether the number of transactions is limited, whether you can hold only one share at a time and what to return if no profit is possible (0).
One transaction: track the lowest price so far and the best difference. Unlimited transactions: add every positive day-to-day rise. Two transactions: keep four running states (buy1, sell1, buy2, sell2).
For each price and each t from 1 to K: buy[t] = max(buy[t], sell[t-1] - price) and sell[t] = max(sell[t], buy[t] + price). The answer is sell[K]. Cost is O(nK).
K = 0, fewer than two prices and a decreasing array return 0. If K >= n/2 the limit never binds, so use the unlimited greedy to avoid large tables.
Solution
O(n*k) time, O(k) space
def max_profit(k, prices):
n = len(prices)
if n < 2 or k == 0:
return 0
if k >= n // 2: # constraint never binds: take every rise
return sum(max(0, b - a) for a, b in zip(prices, prices[1:]))
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) # best state holding a share
sell[t] = max(sell[t], buy[t] + p) # best state after selling
return sell[k]
Tips
- What they are testing: Being tested: how well you generalise from the simple case to a DP. Walk through the variants in order, as the discussion did.
- Common mistake: Resetting state wrongly so the same transaction is counted twice, or filling a table of size K for huge K when K >= n/2 makes it unlimited.
Related Salesforce questions
Collected from public candidate posts and coding forums. Updated Nov 2026.