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.
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: del r 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)) if rm_i == 0: del combined_pro # del target del combined_pro # 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!
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!
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.