☕ DSA Java Articles

Topics › Dynamic Programming › DP on Stocks

Best time to buy and sell stock IV

Medium TUF ID 304 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an integer k and an array prices, where prices[i] is the stock price on day i. You may complete at most k transactions, holding at most one share at a time. Return the maximum profit.

Constraints (LeetCode): 1 ≤ k ≤ 100, 1 ≤ n ≤ 1000, 0 ≤ prices[i] ≤ 1000. The Java file also handles k = 0 and an empty array.

Example 1

k = 2, prices = [2, 4, 1]
answer = 2          // buy 2, sell 4; the 1 at the end cannot be sold

Example 2

k = 2, prices = [3, 2, 6, 5, 0, 3]
answer = 7          // buy 2, sell 6 (+4); buy 0, sell 3 (+3)

This problem contains the earlier ones: k = 1 is the single-transaction problem, k = 2 is Stock III, and k ≥ n / 2 behaves like unlimited transactions, because a trade needs two distinct days.

Approach 1: Recursion

Intuition. Stock III used the state (i, canBuy, cap). That works for any k (with cap up to k), but there is a neater encoding that merges the last two dimensions. Number the operations of a full plan: operation 0 is the first buy, 1 the first sell, 2 the second buy, 3 the second sell, and so on up to 2k - 1. If the next operation number is t, then:

So the state is just (i, t). f(i, t) = best profit from day i onward when the next operation is number t:

The answer is f(0, 0). Because the operation index advances on every buy and every sell, the count of finished transactions is t / 2, and the limit is enforced by the single check t == 2k.

Algorithm.

  1. If i == n or t == 2k, return 0.
  2. Return the maximum of acting today and waiting.
static int recursive(int k, int[] prices) {
    return solve(0, 0, k, prices);
}

static int solve(int i, int t, int k, int[] prices) {
    if (i == prices.length || t == 2 * k) return 0;
    if (t % 2 == 0) {
        return Math.max(-prices[i] + solve(i + 1, t + 1, k, prices),     // buy today
                        solve(i + 1, t, k, prices));                     // skip
    }
    return Math.max(prices[i] + solve(i + 1, t + 1, k, prices),          // sell today
                    solve(i + 1, t, k, prices));                         // keep holding
}

Complexity. Time O(2^n), space O(n) stack.

Approach 2: Memoization

Intuition. The state (i, t) has n × 2k values. Cache them. A small sign variable folds the buy and sell branches into one line: buying pays prices[i], selling receives it. Profits are never negative, so -1 marks “not computed”.

static int memoization(int k, int[] prices) {
    int[][] dp = new int[prices.length][2 * k];
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(0, 0, k, prices, dp);
}

static int memo(int i, int t, int k, int[] prices, int[][] dp) {
    if (i == prices.length || t == 2 * k) return 0;
    if (dp[i][t] != -1) return dp[i][t];
    int sign = (t % 2 == 0) ? -1 : 1;                   // buying pays the price, selling receives it
    int best = Math.max(sign * prices[i] + memo(i + 1, t + 1, k, prices, dp), memo(i + 1, t, k, prices, dp));
    return dp[i][t] = best;
}

Complexity. Time O(n · k): 2nk states with O(1) work. Space O(n · k) plus O(n) stack.

Approach 3: Tabulation

Intuition. f(i, t) reads f(i + 1, t) and f(i + 1, t + 1), both in the next row, so fill rows from i = n - 1 down to 0. Allocate 2k + 1 columns so that column 2k exists and stays 0, which is the “all transactions used” base case. Row n is also all zeros.

Algorithm.

  1. dp[n + 1][2k + 1], all zero.
  2. For i from n - 1 down to 0 and t from 2k - 1 down to 0: dp[i][t] = max(sign · prices[i] + dp[i+1][t+1], dp[i+1][t]).
  3. Return dp[0][0].
static int tabulation(int k, int[] prices) {
    int n = prices.length;
    int[][] dp = new int[n + 1][2 * k + 1];             // dp[n][*] = 0 and dp[*][2k] = 0
    for (int i = n - 1; i >= 0; i--) {
        for (int t = 2 * k - 1; t >= 0; t--) {
            int sign = (t % 2 == 0) ? -1 : 1;
            dp[i][t] = Math.max(sign * prices[i] + dp[i + 1][t + 1], dp[i + 1][t]);
        }
    }
    return dp[0][0];
}

Dry run on k = 2, prices = [3, 2, 6, 5, 0, 3]. Columns are t = 0 (next: buy 1), 1 (sell 1), 2 (buy 2), 3 (sell 2); column 4 is always 0.

i price t = 0 t = 1 t = 2 t = 3
6 - 0 0 0 0
5 3 0 3 0 3
4 0 3 3 3 3
3 5 3 8 3 5
2 6 3 9 3 6
1 2 7 9 4 6
0 3 7 9 4 6

For example dp[3][1] = max(5 + dp[4][2], dp[4][1]) = max(5 + 3, 3) = 8: sell the first share at 5, then still have one full transaction (0 → 3) left. The answer is dp[0][0] = 7.

Complexity. Time O(n · k), space O(n · k).

Approach 4: Space optimised

Intuition. Row i reads only row i + 1, so keep two rows of length 2k + 1 and swap them after each day. This is the same trick used for Stock II and III; the only difference is that the row length now depends on k.

static int spaceOptimized(int k, int[] prices) {
    int[] ahead = new int[2 * k + 1], cur = new int[2 * k + 1];
    for (int i = prices.length - 1; i >= 0; i--) {
        for (int t = 2 * k - 1; t >= 0; t--) {
            int sign = (t % 2 == 0) ? -1 : 1;
            cur[t] = Math.max(sign * prices[i] + ahead[t + 1], ahead[t]);
        }
        int[] tmp = ahead; ahead = cur; cur = tmp;
    }
    return ahead[0];
}

Complexity. Time O(n · k), space O(k).

Edge cases and pitfalls