When k >= len(prices)//2 this problem reduces to the problem type II, so using that solution for that special case.
The thinking behind this code is to generalize the k = 2 case from the problem type III to k > 2.
The sequence of events, can be thought of in chronological order, the stock is traded as the following:
buy1, sell1, buy2, sell2, buy3, sell3...
when buying, we spend money, when selling, we earn the profit, so profits are defined as
profit1 = -buy1 + sell1 (usually we write profit = sell_price - buy_price, but to illustrate the sequence I write buy first)
profit2 = -buy2 + sell2
profit3 = -buy3 + sell3
total money after buy1 = -buy1
total money after sell1 = -buy1 + sell1 = profit1
total money after buy2 = -buy2 + profit1
total money after sell2 = -buy2 + sell2 + profit1 = profit2 + profit1
total money after buy3 = -buy3 + profit2 + profit1
total money after sell3 = -buy3 + sell3 + profit2 + profit1 = profit3 + profit2 + profit1
The lowest price as we traverse through prices list will be assigned transaction 1 so the first one is unique:
if i == 0: buy = min(buy, p) sell[i] = max(sell[i], p - buy[i])
But the rest of the transactions all follow the same pattern for k > 0, after the buy or sell, to maximize the total money currently with:
else: buy[i] = max(buy[i], sell[i - 1] - p) sell[i] = max(sell[i], p + buy[i])
So, in the end, the loop with elements with k > 0 will all behave similarly, and we just need to return the money after the last sell. Here buy and sell indicate the total money after the buy or sell i-th transaction, and p is the buy or sell price. Hope this all makes perfect sense to everyone.
Another leetcoder found a more elegant solution without using the special case of the first transaction reversing k:
but just thought I share my solution since it made more sense in my head.
class Solution(object): def maxProfit(self, k, prices): """ :type k: int :type prices: List[int] :rtype: int """ if not prices or not k: return 0 if k >= len(prices) // 2: profit = 0 for i in range(len(prices) - 1): nextP, currP = prices[i + 1], prices[i] if nextP > currP: profit += max(nextP - currP, 0) return profit buy = [-float('inf')] * k buy = prices sell =  * k for p in prices: for i in range(k): if i == 0: buy = min(buy, p) sell[i] = max(sell[i], p - buy[i]) else: buy[i] = max(buy[i], sell[i - 1] - p) sell[i] = max(sell[i], p + buy[i]) return sell[k - 1]