Cannot find out what subproblems are wrapped. Don't know how to use DP to do it.

My solution is -

Calculate all possible transactions - buy first day, sell 2nd day and same time buy and so on

```
prices [ 1, 2, 0, 2, 3, 2, 8, 9, 4, 3]
profits [ 1, -2, 2, 1, -1, 6, 1, -5, -1]
```

remove negative data from head and tail. combine negative, combine positive

```
combined: [ 1, -2, 2, 1, -1, 7(6+1)]
```

sum of all positive is the max profit.

but there is a K time restriction.

1.search min of |x| in the list.

2.combine previous and next transaction.

3.go to #1 until satisfy K.

sum all positive.

code:

```
class Solution:
def combine_negative_positive(self, a):
r = []
s = 0
for v in a:
if s * v < 0:
r.append(s)
s = v
else:
s += v
r.append(s)
if r[0] <= 0:
del r[0]
if r:
if r[-1] <= 0:
del r[-1]
return r
# @return an integer as the maximum profit
def maxProfit(self, k, prices):
if len(prices) <= 1:
return 0
if k == 0:
return 0
profits = [prices[i] - prices[i-1] for i in range(1, len(prices))]
combined_pro = self.combine_negative_positive(profits)
if not combined_pro:
return 0
while True:
positive_pro = [x for x in combined_pro if x > 0]
if len(positive_pro) <= k:
return sum(positive_pro)
rm_i, rm_v = min([(i, x) for i, x in enumerate(combined_pro)], key=lambda pair: abs(pair[1]))
if rm_i == 0:
del combined_pro[0] # del target
del combined_pro[0] # del next one
elif rm_i == len(combined_pro)-1:
del combined_pro[rm_i] # del target
del combined_pro[rm_i-1] # del previous
else:
combined_pro[rm_i-1] += combined_pro[rm_i] + combined_pro[rm_i+1]
del combined_pro[rm_i] # del target which was added to target's previous
del combined_pro[rm_i] # del next one which was added to target's previous
```