Max Profit With K Transactions

Tags

Max Profit With K Transactions

Category

Dynamic Programming

Difficulty

Very Hard

Problem Statement

Given an array of positive integers representing the prices of a stock on various days, and an integer k, find the maximum profit that can be obtained by making at most k buy-and-sell transactions. A transaction consists of buying on one day and selling on a later day. You must sell a stock before buying again (you cannot hold more than one share at a time).

Intuition

The key insight is that this problem has optimal substructure: the best profit achievable with k transactions up to day d can be built from the best profit with fewer transactions or fewer days. We define a 2D state where one dimension is the number of transactions used and the other is the day. At each day, we either do nothing or complete a transaction by selling, and the buy point for that transaction was chosen optimally from some earlier day. A running maximum trick eliminates the need for a third inner loop, reducing the time complexity from O(k * n^2) to O(k * n).

Approach

  1. Create a 2D table profits[t][d] where t ranges from 0 to k and d ranges from 0 to n-1. profits[t][d] represents the max profit using at most t transactions up to and including day d.
  2. Base cases: profits[0][d] = 0 for all d (zero transactions means zero profit), and profits[t][0] = 0 for all t (only one day means no transaction can complete).
  3. For each transaction count t from 1 to k, maintain a running maximum maxSoFar = -prices[0]. For each day d from 1 to n-1:
    • profits[t][d] = max(profits[t][d-1], prices[d] + maxSoFar)
    • maxSoFar = max(maxSoFar, profits[t-1][d] - prices[d])
  4. The maxSoFar variable tracks the best value of profits[t-1][x] - prices[x] for all x up to the current day. This represents the best "effective buy" considering prior profit.
  5. Return profits[k][n-1].

Pseudocode

function maxProfitWithKTransactions(prices, k):
    if prices is empty:
        return 0

    n = length(prices)
    if k > n / 2:
        // unlimited transactions — greedy
        profit = 0
        for d from 1 to n-1:
            if prices[d] > prices[d-1]:
                profit += prices[d] - prices[d-1]
        return profit

    profits = 2D array of size (k+1) x n, initialized to 0

    for t from 1 to k:
        maxSoFar = -prices[0]
        for d from 1 to n-1:
            profits[t][d] = max(profits[t][d-1], prices[d] + maxSoFar)
            maxSoFar = max(maxSoFar, profits[t-1][d] - prices[d])

    return profits[k][n-1]

Time & Space Complexity

  • Time: O(k * n) where n is the number of days. We iterate through a k x n table with constant work per cell thanks to the running maximum optimization.
  • Space: O(k * n) for the 2D table. This can be reduced to O(n) by noting that row t only depends on row t-1, so only two rows are needed at a time.

Key Insights

  • The running maximum variable maxSoFar absorbs the inner loop that would otherwise scan all prior days for the optimal buy point, reducing time from O(k * n^2) to O(k * n).
  • When k >= n/2, the problem degenerates to "unlimited transactions," which can be solved greedily in O(n) by summing all positive consecutive differences.
  • Each cell encodes a choice: either skip day d (carry forward profits[t][d-1]) or sell on day d (take the best prior buy adjusted by earlier profits).
  • The expression profits[t-1][x] - prices[x] represents the net position if you had completed t-1 transactions optimally and then bought on day x.

Edge Cases

  • Empty prices array: Return 0.
  • k = 0: No transactions allowed, return 0.
  • Single day: No transaction can complete, return 0.
  • k >= n/2: Equivalent to unlimited transactions; switch to greedy approach to avoid unnecessary computation.
  • Monotonically decreasing prices: No profitable transaction exists, return 0.
  • All prices equal: No profit possible, return 0.

Linked mentions