Problem 32.3 · Advanced DPHard

Best Time to Buy and Sell Stock IV

What it teaches: A transaction counter in the state: k (buy, sell) pairs.

Practise it on judges as “Best Time to Buy and Sell Stock IV”.

The problem

At most k transactions (one share at a time). Return the maximum profit.

Example 1

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7

Constraints

1 ≤ k ≤ 100
1 ≤ n ≤ 1000

Pattern clues in the wording

→ Limited number of transactions

These clues point to 1D Dynamic Programming: Define dp[i] as the answer for the first i items, write how it depends on smaller i, and fill it left to right.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int maxProfit(int k, int[] prices) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	k = 2 prices = [2,4,1]	2
2	k = 2 prices = [3,2,6,5,0,3]	7

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. k-layer machine · O(n × k)

k-layer machine

Time O(n × k) Space O(k)

For each price, for j = 1..k: buy[j] = max(buy[j], sell[j − 1] − p); sell[j] = max(sell[j], buy[j] + p).

Approach 1

import java.util.Arrays;

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (k >= n / 2) {
            int profit = 0;
            for (int i = 1; i < n; i++) profit += Math.max(0, prices[i] - prices[i - 1]);
            return profit;
        }
        int[] buy = new int[k + 1], sell = new int[k + 1];
        Arrays.fill(buy, Integer.MIN_VALUE / 2);
        for (int p : prices)
            for (int j = 1; j <= k; j++) {
                buy[j] = Math.max(buy[j], sell[j - 1] - p);
                sell[j] = Math.max(sell[j], buy[j] + p);
            }
        return sell[k];
    }
}

Verdict: Generalises the one- and two-transaction versions.

Before you submit

Edge cases and common mistakes

Test these inputs

k large (unlimited case)
Decreasing prices

Mistakes people make

Allocating n × k × 2 tables when O(k) suffices.

Interview

Follow-up questions

Is there something faster for huge k and n?

Command Palette

The problem

Approaches

k-layer machine

Edge cases and common mistakes

Follow-up questions