```
class Solution(object):
def maxProfit(self, k, prices):
"""
:type k: int
:type prices: List[int]
:rtype: int
"""
n=len(prices)
if n<=1 or k==0:
return 0
prof=[[[0 for i in range(k+1)] for j in range(n)] for m in range(n)]
for i in range(n-1):
min_p=prices[i]
max_p=0
for j in range(i+1,n):
min_p=min(min_p,prices[j])
max_p=max(max_p,prices[j]-min_p)
prof[i][j][1]=max_p
for m in range(2,k+1):
for incr in range(2,n):
for i in range(n-incr):
j=i+incr
re=prof[i][j][m-1]
for cut in range(i+1,j-1):
re=max(re,prof[i][cut][1]+prof[cut+1][j][m-1])
prof[i][j][m]=re
return prof[0][n-1][k]
```