# 188. Best Time to Buy and Sell Stock IV
Say you have an array for which the i-th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Example 1:
Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
Input: [3,2,6,5,0,3], k = 2
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
Approach 1: DP -- as a sequence of separate buy and sell actions.
Approach 2: DP -- modelled for entire transactions.
# Code (Python)
Approach 1:
def maxProfit(self, k: int, prices: List[int]) -> int:
# select at most 2k nums, alternating neg and pos signs, so that sum is maximized
# profit[i][j]: max profit when select j nums from the first i prices
# profit[i][j] = max(profit[i-1][j], profit[i-1][j-1] + (-1)^j * prices[i-1])
if k == 0 or len(prices) < 2:
return 0
if k >= len(prices) // 2:
total = 0
for i in range(1, len(prices)):
total += max(0, prices[i] - prices[i-1])
return total
# need to initialize as neg infinity because buying yields negative profit
profit = [[0] + [-float('inf')] * 2 * k for _ in range(len(prices) + 1)]
for i in range(1, len(prices) + 1):
# for the first i items, can make at most i or 2k actions
for j in range(1, min(i, 2 * k) + 1):
profit[i][j] = max(
profit[i-1][j],
profit[i-1][j-1] + (-1) ** j * prices[i-1]
)
return max(profit[-1])
def maxProfit(self, k: int, prices: List[int]) -> int:
# same idea using 1D
# http://bookshadow.com/weblog/2015/02/18/leetcode-best-time-to-buy-and-sell-stock-iv/
# http://www.cnblogs.com/maples7/p/4350047.html
if 2 * k >= len(prices):
prev = 0
for i in range(1, len(prices)):
prev = prev + max(0, prices[i] - prices[i-1])
return prev
max_prof_at_action = [0] + [-float('inf') for _ in range(2 * k)]
for i in range(len(prices)):
for j in range(1, min(i + 1, 2 * k) + 1):
buy_sell = -1 if j % 2 else 1
max_prof_at_action[j] = max(max_prof_at_action[j], max_prof_at_action[j-1] + prices[i] * buy_sell)
# since we're doing max(..., table[i][j-1] + ...), essentially we're buying/selling then selling/buying at day i, that's why we don't need the max in the return
return max_prof_at_action[2*k]
Approach 2:
def maxProfit(self, k: int, prices: List[int]) -> int:
# profit[i][k]: max profit for the first i days with at most k transactions, k <= 2i
# profit[i][k] = max(profit[m][k-1] + max_once(m + 1, i)) for all m from 1 to i-1 (inclusive)
# profit[i][0] = 0 for all i, profit[0][k] = -inf
# the following code implements the following idea at https://pobenliu.gitbooks.io/leetcode/Best%20Time%20to%20Buy%20and%20Sell%20Stock%20IV.html
# must_sell[i][j]: max profit for day i with at most j transactions, must sell at day i
# max_profit[i][j]: max profit for day i with at most j transactions, can sell or hold
if k >= len(prices) // 2:
total = 0
for i in range(1, len(prices)):
total += max(0, prices[i] - prices[i-1])
return total
must_sell = [[0] * (k + 1) for _ in range(len(prices))]
max_profit = [[0] * (k + 1) for _ in range(len(prices))]
for i in range(1, len(prices)):
for j in range(1, k + 1):
must_sell[i][j] = max(
must_sell[i-1][j] - prices[i-1] + prices[i], # sold yesterday, then buy yesterday and sell today => hold until sell today
max_profit[i-1][j-1] - prices[i-1] + prices[i] # do one more transaction yesterday and today
)
max_profit[i][j] = max(
max_profit[i-1][j], # no transactions today
must_sell[i][j] # do a transaction today
)
return max_profit[-1][-1]
# Code (C++)
Approach 1:
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
if (n < 2 || k < 1)
return 0;
int res = 0;
if (k >= n / 2) // To prevent Memory Limit Exceeded.
{
for (int i = 1; i < n; ++i)
{
if (prices[i] > prices[i-1])
res += prices[i] - prices[i-1];
}
}
else
{
vector<int> buy(k+1, INT_MIN);
vector<int> sell(k+1, 0);
for (int i = 0; i < n; ++i)
{
for (int j = 1; j <= k; ++j)
{
sell[j] = std::max(sell[j], buy[j] + prices[i]);
buy[j] = std::max(buy[j], sell[j-1] - prices[i]);
}
}
for (int i = 1; i <= k; ++i)
{
res = std::max(res, sell[i]);
}
}
return res;
}
};