Description
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: i.e. you may buy at most k times and sell at most k times.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Examples:
Example 1:
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:
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.Solution in Python
To solve this problem, we can use dynamic programming (DP). The idea is to maintain a DP table where dp[i][j] represents the maximum profit achievable with i transactions up to day j. We’ll update this table based on whether we buy, sell, or skip the stock on each day.
Steps to Solve:
- Initialization:
- If
kis 0 or the length ofpricesis 0, the maximum profit is 0 because no transactions can be made. - If
k >= len(prices) // 2, the problem reduces to the problem of “Best Time to Buy and Sell Stock II”, where we can perform as many transactions as needed. This is because with so many transactions allowed, we could buy and sell on every profitable rise.
- If
- DP Table Setup:
- Create a DP table
dpwith dimensions(k+1) x len(prices). - Initialize all values to 0, since with 0 transactions or 0 days, the profit is 0.
- Create a DP table
- DP Table Update:
- Iterate through each possible transaction
i(from 1 tok). - Track the maximum difference
max_diffseen so far, which is the maximum profit from previous transactions minus the price of the stock on the day we bought it. - For each day
j, updatedp[i][j]as the maximum of either not selling today (dp[i][j-1]) or selling today (prices[j] + max_diff).
- Iterate through each possible transaction
- Return Result:
- The result will be in
dp[k][len(prices)-1], representing the maximum profit withktransactions up to the last day.
- The result will be in
Python
from typing import List
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
# Edge cases
if not prices or k == 0:
return 0
n = len(prices)
# If k >= n // 2, it's equivalent to the infinite transactions problem
if k >= n // 2:
max_profit = 0
for i in range(1, n):
if prices[i] > prices[i - 1]:
max_profit += prices[i] - prices[i - 1]
return max_profit
# DP table
dp = [[0] * n for _ in range(k + 1)]
# Fill the DP table
for i in range(1, k + 1):
max_diff = -prices[0]
for j in range(1, n):
dp[i][j] = max(dp[i][j - 1], prices[j] + max_diff)
max_diff = max(max_diff, dp[i - 1][j] - prices[j])
return dp[k][n - 1]Explanation:
- Edge Cases: Handle cases where no prices are given or no transactions are allowed (
k=0). - Infinite Transactions Case: If
kis very large compared to the number of days, it reduces to a simpler problem where we sum up all upward price differences. - DP Table:
dp[i][j]: Max profit withitransactions by the end of dayj.max_diffhelps to efficiently track the best price difference for making a transaction, which is updated for each day as we proceed.
- Time Complexity: O(k * n), where
nis the number of days. - Space Complexity: O(k * n) for the DP table.
Solution in Javascript
JavaScript
/**
* @param {number} k
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(k, prices) {
// Edge case: if prices array is empty or no transactions are allowed
if (prices.length === 0 || k === 0) {
return 0;
}
const n = prices.length;
// If k >= n/2, then we can consider this problem as the "unlimited transactions" case
if (k >= Math.floor(n / 2)) {
let maxProfit = 0;
// Loop through prices to accumulate profit from every increasing pair
for (let i = 1; i < n; i++) {
if (prices[i] > prices[i - 1]) {
maxProfit += prices[i] - prices[i - 1];
}
}
return maxProfit;
}
// DP table: dp[i][j] represents the max profit with at most i transactions by day j
let dp = Array.from({ length: k + 1 }, () => Array(n).fill(0));
// Loop through each transaction
for (let i = 1; i <= k; i++) {
// Initialize maxDiff for the current transaction
let maxDiff = -prices[0];
// Loop through each day
for (let j = 1; j < n; j++) {
// dp[i][j] can either be the profit by not trading today (same as dp[i][j-1])
// or selling today at prices[j] after buying at the best possible price tracked by maxDiff
dp[i][j] = Math.max(dp[i][j - 1], prices[j] + maxDiff);
// Update maxDiff: it's the max of its previous value and the potential new value from dp[i-1][j] - prices[j]
maxDiff = Math.max(maxDiff, dp[i - 1][j] - prices[j]);
}
}
// The answer is in dp[k][n-1], representing max profit with k transactions by the last day
return dp[k][n - 1];
};Solution in Java
Java
class Solution {
public int maxProfit(int k, int[] prices) {
// Edge case: If there are no prices or no transactions are allowed
if (prices.length == 0 || k == 0) {
return 0;
}
int n = prices.length;
// If k is greater than or equal to half the number of days, it's equivalent to unlimited transactions
if (k >= n / 2) {
int maxProfit = 0;
// Calculate the maximum profit by summing up all positive differences between consecutive days
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i - 1]) {
maxProfit += prices[i] - prices[i - 1];
}
}
return maxProfit;
}
// DP array where dp[i][j] represents the max profit using at most i transactions by day j
int[][] dp = new int[k + 1][n];
// Iterate over each number of transactions
for (int i = 1; i <= k; i++) {
// Initialize maxDiff, which is the maximum difference between the profit at day j-1 with i-1 transactions and the price at day j-1
int maxDiff = -prices[0];
// Iterate over each day
for (int j = 1; j < n; j++) {
// The maximum profit on day j with i transactions is either:
// 1. The same as the profit on day j-1 (not making any new transactions)
// 2. The profit gained by selling on day j after buying on the day that gives the best profit possible before j
dp[i][j] = Math.max(dp[i][j - 1], prices[j] + maxDiff);
// Update maxDiff for the next day
maxDiff = Math.max(maxDiff, dp[i - 1][j] - prices[j]);
}
}
// The result is the maximum profit possible with k transactions by the last day
return dp[k][n - 1];
}
}Solution in C#
C#
public class Solution {
public int MaxProfit(int k, int[] prices) {
// Edge case: if prices array is empty or no transactions are allowed
if (prices.Length == 0 || k == 0) {
return 0;
}
int n = prices.Length;
// If k >= n/2, then we can consider this problem as the "unlimited transactions" case
if (k >= n / 2) {
int maxProfit = 0;
// Loop through prices to accumulate profit from every increasing pair
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i - 1]) {
maxProfit += prices[i] - prices[i - 1];
}
}
return maxProfit;
}
// DP table: dp[i][j] represents the max profit with at most i transactions by day j
int[,] dp = new int[k + 1, n];
// Loop through each transaction
for (int i = 1; i <= k; i++) {
// Initialize maxDiff for the current transaction
int maxDiff = -prices[0];
// Loop through each day
for (int j = 1; j < n; j++) {
// dp[i][j] can either be the profit by not trading today (same as dp[i][j-1])
// or selling today at prices[j] after buying at the best possible price tracked by maxDiff
dp[i, j] = Math.Max(dp[i, j - 1], prices[j] + maxDiff);
// Update maxDiff: it's the max of its previous value and the potential new value from dp[i-1][j] - prices[j]
maxDiff = Math.Max(maxDiff, dp[i - 1, j] - prices[j]);
}
}
// The answer is in dp[k, n-1], representing max profit with k transactions by the last day
return dp[k, n - 1];
}
}