The Maximum Profit with K Transactions is a classic dynamic programming problem that asks us to find the maximum profit that can be obtained by purchasing and selling stocks up to k times, with restrictions that we cannot sell before we buy and cannot have more than one transaction ongoing at any point in time.
To solve this problem using dynamic programming, we can use a 2D array to keep track of the maximum profit that can be obtained up to each transaction and each day. Let’s call this array "dp."
The first dimension of "dp" represents the number of transactions made so far, and the second dimension represents the current day. For example, "dp[i][j]" will represent the maximum profit that can be obtained up to and including the jth day, using exactly i transactions.
To compute the value of "dp[i][j]," we consider two cases:
1. We don’t make a transaction on the jth day. In this case, the value of "dp[i][j]" is the same as "dp[i][j-1]" since we don’t change anything by not making any trades.
2. We make a transaction on the jth day. In this case, we need to determine the maximum profit that can be obtained by purchasing a stock on any day "m" <= "j" and selling it on day "j." We can compute the profit by subtracting the stock’s purchase price from its selling price.
To do this, we can iterate over all possible days "m" less than or equal to "j." For each "m," we can compute the maximum profit that can be obtained up to day "m-1" using "i-1" transactions (since we’re using one more transaction than in our current state), and then add the profit gained from purchasing the stock on day "m" and selling it on day "j."
By taking the maximum over all possible values of "m," we obtain the maximum profit that can be obtained with i transactions and selling on the jth day, allowing us to update "dp[i][j]."
Finally, to solve the problem, we return the value of "dp[k][n-1]," where "n" is the length of the given prices array.
Here’s the Java code, assume prices is a given array of prices of stocks on each day:
public int maxProfit(int k, int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int n = prices.length;
int[][] dp = new int[k+1][n];
for (int i = 1; i <= k; i++) {
int maxProfit = -prices[0];
for (int j = 1; j < n; j++) {
dp[i][j] = Math.max(dp[i][j-1], prices[j] + maxProfit);
maxProfit = Math.max(maxProfit, dp[i-1][j-1] - prices[j]);
}
}
return dp[k][n-1];
}In this code, we initialize the first row of "dp" to be 0, since we cannot make any transactions with 0 days. Then, we iterate over each pair (i, j), starting from (1, 1) to compute "dp[i][j]" using the two cases described above. Once the iteration is complete, "dp[k][n-1]" will contain the maximum profit that can be obtained up to the nth day with k transactions.