Definitely not DP


  • 0
    A

    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

  • 0
    F

    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!


  • 0
    A
    This post is deleted!

  • 0
    Q

    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!


  • 0
    L

    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.


Log in to reply
 

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