Best Time to Buy and Sell Stock III

Question

Say you have an array for which the $$i_{th}$$ element is the price of a given stock on day $$i$$.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Tag

• Array
• Dynamic Programming
• Divide and Conquer

Thought

This is the hardest one among the "buy and sell stock" questions. The hard part is that the transaction time is at most twice.

Since these two transactions are not allow to have overlapping in the time stamp, we can use divide and conquer method to chop this array into two parts and find the maximum profit for each part.

With the DP memo, duplicated calculation can be avoided and the time complexity will be O(n).

However, this approach can only solve this problem. What if the maximum number of transactions is 3, or 4, or k? It is better to provide a more universal solution.

With the explanation by Code Ganker(This explanation is in Chinese), a more universal algorithm is implemented here.

In the implementation, two arrays are defined: global_profit and local_profit. The global_profit[i][j] represents the maximum profits in the price array with i items and j maximum transaction numbers. The local_profit[i][j] also represents almost the same meaning. The difference between them is that local_profit must consider the price of the last item. The relation between them can be described with the equation below:

local_profit[i][j]=max(global_profit[i-1][j-1]+max(diff,0),local_profit[i-1][j]+diff) global_profit[i][j]=max(local_profit[i][j],global_profit[i-1][j]) where diff is the difference between the prices of the last two days: diff=prices[i]-prices[i-1].

Here, the maximum number of the transactions is 2, thus the length of the array for global_profit and local_profit is all 3(We don't need two tables for them to store all the data, because we only care with the whole prices array).

Code

Use the divide-and-conquer approach:

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        length = len(prices)
        if length <= 1:
            return 0
        DP_order = [0 for i in xrange(length)]
        DP_reverse = [0 for i in xrange(length)]
        minPrice = prices[0]
        for i in xrange(1, length):
            minPrice = min(prices[i], minPrice)
            DP_order[i] = max(prices[i] - minPrice, DP_order[i - 1])
        maxPrice = prices[-1]
        for i in xrange(length - 2, -1, -1):
            maxPrice = max(prices[i], maxPrice)
            DP_reverse[i] = max(maxPrice - prices[i], DP_reverse[i + 1])
        maxProfit = 0
        for i in xrange(length):
            if i == 0:
                maxProfit = DP_reverse[i]
            else:
                maxProfit = max(maxProfit, DP_order[i - 1] + DP_reverse[i])
        return maxProfit

Use the universal approach:

class Solution(object):
    def maxProfit(self, prices):
        """

        global[i][j]=max(local[i][j],global[i-1][j])，

        local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff)

        :type prices: List[int]
        :rtype: int
        """
        length = len(prices)
        if length == 0:
            return 0
        local_profit = [0] * 3
        global_profit = [0] * 3
        for i in xrange(length - 1):
            diff = prices[i + 1] - prices[i]
            for j in range(2, 0, -1):
                local_profit[j] = max(global_profit[j - 1] + max(diff, 0), local_profit[j] + diff)
                global_profit[j] = max(local_profit[j], global_profit[j])
        return global_profit[2]