Buy and Sell Stock IV
Find the best time to buy and sell stock to achieve maximum profit.
You are given an integer array prices
where prices[i]
is the price of a given stock on the i
th 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).
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
@cache
def max_profit(i, k, stock_in_hand):
if not i or k < 1:
return 0 if not stock_in_hand else -prices[i]
if stock_in_hand:
return max(max_profit(i - 1, k, True), max_profit(i - 1, k - 1, False) - prices[i])
else:
return max(max_profit(i - 1, k, False), max_profit(i - 1, k, True) + prices[i])
return max_profit(len(prices) - 1, k, False)