Stock Trader with K Transactions

Problem

You are given an integer array prices where prices[i] represents the price of a stock on day i, and an integer k representing the maximum number of transactions you are allowed to make.

A transaction consists of buying one share of the stock and later selling it. You may not engage in multiple transactions simultaneously — you must sell the stock before you buy again.

Return the maximum profit you can achieve with at most k transactions.

Input / Output Format

Function signature:

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

• Input: An integer k and a list of integers prices
• Output: An integer representing the maximum achievable profit

Examples

Example 1

Input: k = 2, prices = [2, 4, 1, 7] Output: 8 Explanation: Buy on day 1 (price=2), sell on day 2 (price=4) → profit = 2. Buy on day 3 (price=1), sell on day 4 (price=7) → profit = 6. Total = 8.

Example 2

Input: k = 1, prices = [3, 2, 6, 5, 0, 3] Output: 4 Explanation: Buy on day 2 (price=2), sell on day 3 (price=6) → profit = 4. Only 1 transaction allowed.

Example 3

Input: k = 2, prices = [3, 3, 5, 0, 0, 3, 1, 4] Output: 6 Explanation: Buy on day 4 (price=0), sell on day 6 (price=3) → profit = 3. Buy on day 7 (price=1), sell on day 8 (price=4) → profit = 3. Total = 6.

Approach Hints

1. Brute Force (O(n²·k)): Try every combination of buy/sell days — this will time out for large inputs.

2. Dynamic Programming: Define dp[t][d] as the maximum profit using at most t transactions up to day d. The recurrence is:

   • dp[t][d] = max(dp[t][d-1], max over j<d of (prices[d] - prices[j] + dp[t-1][j]))
   • Optimize the inner max to O(1) by tracking a running best_so_far value.

3. Key Insight — Unlimited Transactions: If k >= n/2, you can make as many transactions as you want, so simply sum all positive differences between consecutive days.