Problem

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Examples

Example 1:

1
2
3
4

Input: k = 2, prices = [2,4,1]
Output:
 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

1
2
3
4
5

Input:
k = 2, prices = [3,2,6,5,0,3]
Output:
 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

We have already seen - Best Time To Buy And Sell Stock 3 - at most twice. This is the generic version of that.

Solution

Method 1 - Recursion

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

    public int dfs(int k, int n, int[] prices) {
        if (k == 0 || n == 0)
            return 0; // if any of then becomes 0, no profit

        int curr = prices[n - 1], profit = 0;

        // Finding max profit for current day. As we are moving backwards, if we
        // sell on day let say x, and purchase it on y (where y<x) then the next
        // possible transaction would be from day y. That's why we use function
        // solve() again while getting our profit. Also as we have transacted
        // once, we reduce the value of k.
        for (int i = n - 1; i >= 0; i--) {
            profit =
                Math.max(profit, (curr - prices[i]) + dfs(k - 1, i, prices));
        }
        // if we decide not to transact on that day, we simply reduce n, else go
        // with our 'profit'.
        return Math.max(dfs(k, n - 1, prices), profit);
    }
}

Method 2 - Top Down DP with Memoization

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[][] dp = new int[k + 1][n + 1];
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }
        return dfs(k, n, prices, dp);
    }

    public int dfs(int k, int n, int[] prices, int[][] dp) {
        if (k == 0 || n == 0) {
            return 0; // No profit if either k or n is zero
        }
        if (dp[k][n] != -1) {
            return dp[k][n];
        }

        int curr = prices[n - 1];
        int maxProfit = 0;

        // Calculate max profit for the current day.
        // By moving backwards and selling on day p, buying on day q (where q <
        // p), the next transaction would start from day q. Each time we
        // transact, k is decreased by 1.
        for (int i = n - 1; i >= 0; i--) {
            maxProfit = Math.max(
                maxProfit, (curr - prices[i]) + dfs(k - 1, i, prices, dp));
        }

        // If no transaction on the current day, proceed by reducing n;
        // otherwise, use the computed maxProfit.
        dp[k][n] = Math.max(dfs(k, n - 1, prices, dp), maxProfit);
        return dp[k][n];
    }
}

Method 3 - DP

Let’s create a dp array of size [k+1][n]. For any t in [1, k] and i in [1, n):

Let dp[t][i] denote the maximum profit using at most t transactions up to day i (inclusive). The relation can be expressed as:

1
2
3
4
5
6

dp[t][i] = max(dp[t][i-1], max(prices[i] - prices[j] + dp[t-1][j]))
for all j in the range [0, i-1]

dp[t][i-1] -> If no transaction is made on day i

dp[t-1][j] -> Best profit possible with t-1 transactions on day j

To summarize, dp[t][i] is the maximum of:

  1. dp[t][i-1], representing the scenario where no transaction is made on the ith day.
  2. The maximum profit from selling on the ith day. To sell shares on the ith day, they must be bought on any day in the range [0, i-1]. If shares are bought on the jth day and sold on the ith day, the maximum profit is prices[i] - prices[j] + dp[t-1][j], where j varies from 0 to i-1. Here, dp[t-1][j] represents the best we could have done with one less transaction by the jth day.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public int maxProfit(int k, int[] prices) {
	if (prices == null || prices.length == 0) {
		return 0;
	}

	int maxProfit = 0;
	int n = prices.length;
	int[][] dp = new int[k + 1][n];
	for (int t = 1; t<= k; t++) {
		for (int i = 1; i<n; i++) {
			for (int j = 0; j<i; j++) {
				dp[t][i] = Math.max(dp[t][i], prices[i] - prices[j] + dp[t - 1][j]);
			}
			dp[t][i] = Math.max(dp[t][i], dp[t][i - 1]);
		}

	}
	return dp[k][n - 1];
}

Complexity

  • ⏰ Time complexity: O(k.n^2)
  • 🧺 Space complexity: O(k.n)

Method 4 - Optimized DP

The previous solution has a time complexity of O(k * n^2). However, this can be optimized to calculate the maximum profit from selling shares on the ith day in constant time.

Consider the previous DP relation:

1
2

dp[t][i] = max(profit [t][i-1], max(prices[i] – prices[j] + dp[t-1][j]))
 for all j in range [0, i-1]

Notice that:

1
2

max(prices[i] – prices[j] + dp[t-1][j])
for all j in range [0, i-1]

can be rewritten as:

1
2
3
4
5
6
7
8

= prices[i] + max(dp[t-1][j] – prices[j])
for all j in range [0, i-1]

= prices[i] + max(prevDiff, dp[t-1][i-1] – prices[i-1])

where prevDiff is max(dp[t-1][j] – prices[j])

for all j in range [0, i-2]

If we’ve already computed max(dp[t-1][j] - prices[j]) for all j in the range [0, i-2], then we can calculate it for j = i-1 in constant time. This eliminates the need to look back through the range [0, i-1] to find the best day to buy. Instead, we can determine it in constant time using this revised relation:

1
2

dp[t][i] = max(dp[t][i-1], prices[i] + max(prevDiff, dp[t-1][i-1] - prices[i-1]))
where prevDiff is max(dp[t-1][j] - prices[j]) for all j in the range [0, i-2]

To summarize:

1
2
3

maxDiff = Max(maxDiff,dp[t-1][i-1] - prices[i-1])

dp[t][i] = Max(dp[t][i-1],prices[i]+maxDiff)
  • dp[t][i-1]: If no transaction is made on the ith day
  • prices[i] - prices[j] + dp[t-1][j]: If a transaction is made on the ith day, compute maxDiff for the range [0, i-1]. This reuses the previously computed maxDiff, reducing the time complexity to O(n).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

public int maxProfit(int k, int[] prices) {
	if (prices.length == 0)
		return 0;
	int n = prices.length;
	int dp[][] = new int[k + 1][n];
	for (int t = 1; i<= k; t++) {
		int maxDiff = dp[t - 1][0] - prices[0];
		for (int i = 1; i<n; i++) {
			maxDiff = Math.max(maxDiff, dp[t - 1][i - 1] - prices[i - 1]);
			dp[t][i] = Math.max(dp[t][i - 1], prices[j] + maxDiff);
		}
	}
	return dp[k][n - 1];
}

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public int maxProfit(int k, int[] prices) {
	if (prices == null || prices.length == 0) {
		return 0;
	}

	if (k >= prices.length / 2) {
		return quickSolve(prices);
	}
	
	int[][] dp = new int[k + 1][prices.length];
	
	for (int t = 1; t <= k; t++) {
		int max = Integer.MIN_VALUE;
		for (int j = 1; j < prices.length; j++) {
			dp[i][j] = Math.max(dp[i][j - 1], prices[j] + max);
			tmpMax = Math.max(tmpMax, dp[i - 1][j] - prices[j]);
		}
	}
	return dp[k][prices.length - 1];
}
// BestTimeToBuyAndSellStock2 - maxprofit
private int quickSolve(int[] prices) {
	int maxProfit = 0;
	for (int i = 1; i < prices.length; i++) {
		if (prices[i] > prices[i - 1])
			maxProfit += prices[i] - prices[i - 1];
	}
	return maxProfit;
}

Complexity

  • ⏰ Time complexity: O(k.n)
  • 🧺 Space complexity: O(k.n)

Space complexity can be optimized to O(n) by utilizing the results from the previous transaction.

Method 5 - 1D Dynamic Programming

The solution above can be simplified to be the following:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public int maxProfit(int k, int[] prices) {
	if (prices.length<2 || k<= 0)
		return 0;

	int[] local = new int[k + 1];
	int[] global = new int[k + 1];

	for (int i = 0; i<prices.length - 1; i++) {
		int diff = prices[i + 1] - prices[i];
		for (int j = k; j >= 1; j--) {
			local[j] = Math.max(global[j - 1] + Math.max(diff, 0), local[j] + diff);
			global[j] = Math.max(local[j], global[j]);
		}
	}

	return global[k];
}

Complexity

  • ⏰ Time complexity: O(k.n)
  • 🧺 Space complexity: O(k)

Method 6 - DP with State Machine

The idea is to design a state machine that accurately represents the problem. There are three possible actions:

  • Rest: Do nothing
  • Buy
  • Sell

When no stock has been bought, we are in a rest state. From here, we can either remain resting or buy a stock. If we own stock, we can either rest or sell it.

Here is the state machine for 2 transactions (k=2):

stateDiagram-v2
	direction LR
    0 --> 1: BUY
    1 --> 2: BUY
    2 --> 3: BUY
    3 --> 4: BUY

	0 --> 0: REST
	1 --> 1: REST
	2 --> 2: REST
	3 --> 3: REST
    
    classDef finalState fill:purple
    class 4 finalState

Understanding the state diagram for k = 2: We start at state 0, where we can either rest (do nothing) or buy stock at the current price.

  • Resting keeps us in state 0.
  • Buying moves us to state 1 and deducts the stock price from our funds.

In state 1, we can either rest or sell our stock.

  • Resting keeps us in state 1.
  • Selling earns us money (stock price of the day) and moves us to state 2.

This completes one transaction. With k-1 transactions remaining, we move to the next steps.

In state 2, we can again choose to rest or buy more stock.

  • Resting keeps us in state 2.
  • Buying moves us to state 3.

In state 3, the options are once again to rest or make the final sale.

  • Resting keeps us in state 3.
  • Selling completes our transactions and moves us to the final state 4.

Translating the state diagram into code

1
2
3
4
5
6
7
8

// Assuming we are in state S
// For buying, we spend money; alternatively, we can do nothing
// Doing nothing: S->S
// Buying: X->S, with a cost
S = max(S, X-prices[i])

// For selling a stock, the situation is similar
S = max(S, X+prices[i])

For generic k: For k = 2 transactions, there are 4 states. Similarly, for k transactions, there are 2k possible states.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public int maxProfit(int[] prices) {
	int INITIAL_AMOUNT = 0;
	int s1 = 0;
	int s2 = 0;
	int s3 = 0;
	int s4 = 0;
	int p = 0;

	for (int price: prices) {
		s1 = Math.max(s1, INITIAL_AMOUNT - price);
		s2 = Math.max(s2, s1 + price);
		s3 = Math.max(s3, s2 - price);
		s4 = Math.max(s4, s3 + price);
		p = s4 - INITIAL_AMOUNT;
	}

	return p;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

private int maxProfit(int k, int[] prices) {
	int[] stock = new int[k * 2];
	Arrays.fill(stock, Integer.MIN_VALUE);
	stock[0] = -prices[0];
	for (int i = 1; i<prices.length; ++i) {
		stock[0] = Math.max(stock[0], -prices[i]);
		for (int j = 1; j<2 * k; j += 2) {
			stock[j] = Math.max(stock[j], stock[j - 1] + prices[i]);
			if (j + 1<2 * k) {
				stock[j + 1] = Math.max(stock[j + 1], stock[j] - prices[i]);
			}
		}
	}
	return Math.max(0, stock[2 * k - 1]);
}

Complexity

  • ⏰ Time complexity: O(k.n)
  • 🧺 Space complexity: O(k)

Method 7 - Using State Machine and Recursion + Memo

This problem resembles the knapsack problem with three variables: current index, remaining transactions, and whether a stock is already bought. Based on these variables, we have three possible actions:

  1. Do nothing.
  2. If a stock is already bought, sell it.
  3. Buy the current stock and ignore the previously bought stock.

Base condition: if the index is out of range or the transaction limit is reached.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public int maxProfit(int k, int[] prices) {
	// Last 2 stands for isBought
	int[][][] memo = new int[prices.length][k+1][2];
	for(int i=0; i<prices.length; i++)
		for(int j=0; j<k+1; j++)
			for(int m=0; m<2; m++)
				memo[i][j][m] = -1;
	
	return dfs(k, prices, 0, 0);
}

private int dfs(int k, int[] prices, int idx, int isBought)
{
	if(idx >= prices.length || tran == 0)
		return 0;
	
	// DP
	int bought = isBought == true ? 1 : 0;
	if(memo[idx][k][bought] != -1)
		return memo[idx][k][bought];
	
	// Do nothing
	int profit = helper(k, prices, idx+1, isBought);
	
	if(isBought)    // Sell share
		profit = Math.max(profit, helper(k-1, prices, idx+1, false) + prices[idx]);
	
	// Buy share
	profit = Math.max(profit, dfs(k, prices, idx+1, true) - prices[idx]);
	
	memo[idx][k][bought] = profit;
	return profit;
}

Method 8 - State Machine and DP Tabulation

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public int maxProfit(int k, int[] price) {
	int n = price.length;

	int dp[][][] = new int[n + 1][2][k+1];
	for (int i = 0; i<n; i++)
		for (int j = 0; j<2; j++)
			for (int k = 0; k<3; k++)
				dp[i][j][k] = 0;

	//Tabulation
	for (int ind = n - 1; ind >= 0; ind--) {
		for (int buy = 0; buy<= 1; buy++) {
			for (int cap = 1; cap<= k; cap++) {
				if (buy == 1) {
					dp[ind][buy][cap] = Math.max(-price[ind] + dp[ind + 1][0][cap], 0 + dp[ind + 1][1][cap]);
				} else {
					dp[ind][buy][cap] = Math.max(price[ind] + dp[ind + 1][1][cap - 1], 0 + dp[ind + 1][0][cap]);
				}
			}
		}
	}

	return dp[0][1][k];
}