DSA interview question

Best Time to Buy and Sell Stock IV

Medium · Algorithms · Topics: dynamic programming, array

The problem

You're extending the trading bot backend from before, but now the compliance team has imposed a hard cap: the bot is only allowed to execute at most k transactions (a transaction = one buy followed by one sell) in the given trading window. Given an array prices where prices[i] is the stock price on day i, and an integer k, return the maximum profit achievable with at most k transactions. You can hold at most one share at a time (must sell before buying again).

Function signature

int maxProfit(int k, vector<int>& prices);

Test cases

Input `k`	Input `prices`	Output	Explanation
`2`	`[2,4,1]`	2	Buy@2, sell@4 (profit 2); second transaction not worth it
`2`	`[3,2,6,5,0,3]`	7	Buy@2, sell@6 (profit 4), buy@0, sell@3 (profit 3) → total 7
`1`	`[7,1,5,3,6,4]`	5	Buy@1, sell@6 (profit 5), only 1 transaction allowed
`0`	`[1,2,3,4,5]`	0	No transactions allowed
`100`	`[1,2,3,4,5]`	4	k is large relative to array — behaves like unlimited transactions
`2`	`[]`	0	Empty array
`3`	`[1]`	0	Single day — no transaction possible

(Always check the case where k is very large relative to n/2 — that's a classic optimization trap discussed below.)

How interviewers phrase it

"You can complete at most k buy-sell transactions. Maximize profit."
"This generalizes 'Best Time to Buy and Sell Stock III' (k=2) — now k is an arbitrary input."
They may follow up by asking you to first solve for k=1, then k=2, then generalize — testing whether you see the pattern.

Clarifying questions to ask

Can I hold at most one share at a time (must sell before buying again)?
Does a transaction mean one buy+sell pair, or is buy and sell counted separately?
What's the range of k relative to n (array length)? This matters a lot — if k >= n/2, the problem collapses to the unlimited-transactions case.
Are prices non-negative integers? Can k be 0?
Is k potentially very large (e.g., up to 10^9)? This affects whether the O(nk) DP is feasible or whether you need the greedy fallback for large k.

Follow-ups to expect

"What if k is larger than n/2?"
"Can you reduce space from O(nk) to O(k)?"
"How does this generalize from k=1 (Stock I) and k=2 (Stock III)?"
"What if there's also a transaction fee, like in the fee variant?"
"What if there's a cooldown after selling?"
"Can you prove why buying and selling on the same day is never beneficial?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview