# Definitely not DP

• 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``````

• How about removing the min of positive transaction before combining it with the min of adjacent negative transaction? The Combining can't reduce the amount of the transactions!

• This post is deleted!

• It sounds like a brilliant idea. I'm trying to implement based on that, but fail to pass some test case. Could you kindly share the implementation? Thanks!

• Good Idea, but to me it's still DP, originated from max times of buy/sell, and the sub-problem is to find out the Minimum of Merging lost.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.