```
class Solution(object):
def maxProfit(self, k, prices):
if len(prices) < 2: return 0
if k < len(prices) / 2:
buy = [-1e18] * (k + 1)
sell = [0] * (k + 1)
for price in prices:
for i in range(1, k + 1):
sell[i] = max(sell[i], buy[i] + price)
buy[i] = max(buy[i], sell[i - 1] - price)
return max(sell)
else:
prof = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
prof += prices[i] - prices[i - 1]
return prof
```

I formulated this idea based on the solution for Buy and Sell Stock III where some solutions explained a state machine. We define the following dp functions:

```
buy[i][j] = Maximum profit at to buy stock at index i while making j'th buy tranxn
sell[i][j] = Maximum profit at to buy stock at index i while making j'th sell tranxn
```

DP equations:

```
sell[i][j] = max(sell[i][j], buy[i - 1][j] + price[i])
buy[i][j] = max(buy[i][j], sell[i][j - 1] - price[i])
```

Since state for each j depends on only previous state (i - 1)

For each price:

```
sell[j] = max(sell[j], buy[j] + price)
buy[j] = max(buy[j], sell[j - 1] - price)
```

For the case k > len / 2 I follow similar approach as by the best answers to calculate maximum profit by collecting all possible increase in stock price.