A chronological and intuitive solution with explanation time O(k*n) space O(k)


  • 0
    G

    When k >= len(prices)//2 this problem reduces to the problem type II, so using that solution for that special case.
    The thinking behind this code is to generalize the k = 2 case from the problem type III to k > 2.
    The sequence of events, can be thought of in chronological order, the stock is traded as the following:

    buy1, sell1, buy2, sell2, buy3, sell3...

    when buying, we spend money, when selling, we earn the profit, so profits are defined as
    profit1 = -buy1 + sell1 (usually we write profit = sell_price - buy_price, but to illustrate the sequence I write buy first)
    profit2 = -buy2 + sell2
    profit3 = -buy3 + sell3
    ...
    total money after buy1 = -buy1
    total money after sell1 = -buy1 + sell1 = profit1
    total money after buy2 = -buy2 + profit1
    total money after sell2 = -buy2 + sell2 + profit1 = profit2 + profit1
    total money after buy3 = -buy3 + profit2 + profit1
    total money after sell3 = -buy3 + sell3 + profit2 + profit1 = profit3 + profit2 + profit1
    ...

    The lowest price as we traverse through prices list will be assigned transaction 1 so the first one is unique:

                    if i == 0:
                        buy[0] = min(buy[0], p)
                        sell[i] = max(sell[i], p - buy[i])
    

    But the rest of the transactions all follow the same pattern for k > 0, after the buy or sell, to maximize the total money currently with:

                    else:
                        buy[i] = max(buy[i], sell[i - 1] - p)
                        sell[i] = max(sell[i], p + buy[i])
    

    So, in the end, the loop with elements with k > 0 will all behave similarly, and we just need to return the money after the last sell. Here buy and sell indicate the total money after the buy or sell i-th transaction, and p is the buy or sell price. Hope this all makes perfect sense to everyone.

    Another leetcoder found a more elegant solution without using the special case of the first transaction reversing k:
    https://discuss.leetcode.com/topic/23888/concise-python-solution-with-detailed-explanation-o-kn-time-o-k-space
    but just thought I share my solution since it made more sense in my head.

    Complete code:

    class Solution(object):
        def maxProfit(self, k, prices):
            """
            :type k: int
            :type prices: List[int]
            :rtype: int
            """
            if not prices or not k:
                return 0
            if k >= len(prices) // 2:
                profit = 0
                for i in range(len(prices) - 1):
                    nextP, currP = prices[i + 1], prices[i]
                    if nextP > currP:
                        profit += max(nextP - currP, 0)
                return profit
            buy = [-float('inf')] * k
            buy[0] = prices[0]
            sell = [0] * k
            for p in prices:
                for i in range(k):
                    if i == 0:
                        buy[0] = min(buy[0], p)
                        sell[i] = max(sell[i], p - buy[i])
                    else:
                        buy[i] = max(buy[i], sell[i - 1] - p)
                        sell[i] = max(sell[i], p + buy[i])
            return sell[k - 1]
    

Log in to reply
 

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