188. Best Time to Buy and Sell Stock IV
def maxProfit(self, k: int, prices: List[int]) -> int:
# DP
# O(nk)time O(k)space
if k==0 or len(prices)<=1:
return 0
#Q2 Approach 3
if 2*k >= len(prices):
profit = 0
for i in range(1, len(prices)):
if prices[i]>prices[i-1]:
profit += prices[i]-prices[i-1]
return profit
#Q3 Approach 2 extension
costs = [float('inf')] * k
profits = [0] * k
costs[0] = prices[0]
for i in range(1, len(prices)):
for j in range(k):
if j==0:
costs[j] = min(costs[j], prices[i]) #buy
profits[j] = max(profits[j], prices[i]-costs[j]) #sell
else:
costs[j] = min(costs[j], prices[i]-profits[j-1]) #buy # the minimum cost for jth buy at location i
profits[j] = max(profits[j], prices[i]-costs[j]) #sell # the maximum cost for jth sell at location i
return profits[k-1]
Use Kadane's algorithm
def maxProfit(self, k: int, prices: List[int]) -> int:
N = len(prices)
if N <= 1:
return 0
if N <= 2 * k:
return sum([max(0, prices[i] - prices[i - 1]) for i in range(1, N)])
pnl = [0] * N
price_diff = [prices[i] - prices[i - 1] for i in range(1, N)]
for _ in range(k):
val = 0
for i in range(1, N):
val = max(pnl[i], val + price_diff[i - 1])
pnl[i] = max(pnl[i - 1], val)
return pnl[-1]
def maxProfit(self, k: int, prices: List[int]) -> int:
N = len(prices)
@cache
def partialMaxProfit(i, maxTimes):
if N - i <= 1:
return 0
if maxTimes == 0:
return 0
if N - i <= 2 * maxTimes:
return sum([max(0, prices[j] - prices[j - 1]) for j in range(i + 1, N)])
res = partialMaxProfit(i + 1, maxTimes)
for j in range(i + 1, N):
res = max(res, prices[j] - prices[i] + partialMaxProfit(j + 1, maxTimes - 1))
return res
return partialMaxProfit(0, k)