Katkat
Back

Maximum stock trading profit with at most k buy-and-sell transactions

OracleSoftware Engineer · Other
MediumSoftware EngineerOtherCoding & Algorithms

Last updated

Given daily stock prices and a transaction limit k, compute the maximum profit achievable with at most k buy-then-sell trades while holding at most one share at a time. It tests generalizing a fixed-count trading problem, handling a k larger than the available profitable trades, and tracking state efficiently.

You are given an integer k and a list prices, where prices[i] is the price of one share of a stock on day i. You may complete at most k transactions, where a transaction means buying one share and later selling it. Return the maximum total profit you can achieve.

Function Signature

def max_profit_k_transactions(k: int, prices: List[int]) -> int:

Rules

  • You can hold at most one share at a time, so you must sell before buying again.
  • A sale and the next purchase may happen on the same day.
  • Any number of transactions from zero up to k is allowed; if no trade makes money, return 0.
  • k may exceed the number of profitable trades available; the extra allowance simply goes unused.

Constraints

  • 1 <= k <= 100
  • 1 <= len(prices) <= 1000
  • 0 <= prices[i] <= 1000

Examples

Example 1

Input: k = 2, prices = [3, 8, 2, 6, 1, 9]
Output: 13

Buy at 3 and sell at 8 for 5, then buy at 1 and sell at 9 for 8. Pairing the rise from 2 to 6 with either of the others earns less.

Example 2

Input: k = 3, prices = [3, 8, 2, 6, 1, 9]
Output: 17

With a third transaction allowed, all three rises can be taken: 5 + 4 + 8.

Example 3

Input: k = 1, prices = [4, 2, 7, 1, 3]
Output: 5

The single best trade buys at 2 and sells at 7.