Leetcode 123. Best Time to Buy and Sell Stock III

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

Now this is much harder. The simple thought is to divide and conquer: break the list into two parts and then get the profit and try out every possible break points. But this solution will get TLE (time limit exceeded) for O(n^2) complexity.

Thus there are two ways out: one is to use a more efficient way sticking to that thought, another is to change method. Below solution 1 is the short way, while it is subtle and hard to get; solution 2 is an improved way of original thought using DP.

For explanation of solution 1, hold i means the profit it will make if it is the ith time to hold.  Note that not necessarily it will buy or sell at that point. From this aspect, we should read the program bottom up: hold 1 means first buy of lowest price, and after buying the profit is of course negative; release 1 means max profit it can make in the first tract till here. Hold 2 and release 2 are the same things. Their sequence is limited by the assignment sequence, which is very smart design: it will not achieve max profit buying and selling at the same price, so there will be at least one distance from hold and release, thus those 4 actions will not go intersection.

Solution 1:

# T:O(n) S:O(1)
class Solution:
    # @param prices, a list of integer
    # @return an integer
    def maxProfit(self, prices):
        hold1, hold2 = float("-inf"), float("-inf")
        release1, release2 = 0, 0
        for i in prices:
            release2 = max(release2, hold2 + i)
            hold2    = max(hold2,    release1 - i)
            release1 = max(release1, hold1 + i)
            hold1    = max(hold1,    -i);
        return release2

Run Time: 68 ms

Solution 2:

# T:O(n) S:O(n)
class Solution:
    # @param prices, a list of integer
    # @return an integer
    def maxProfit(self, prices):
        length=len(prices)
        if length==0: return 0
        f1=[0 for i in range(length)]
        f2=[0 for i in range(length)]
        
        minV=prices[0]; f1[0]=0
        for i in range(1,length):
            minV=min(minV, prices[i])
            f1[i]=max(f1[i-1],prices[i]-minV)
            
        maxV=prices[length-1]; f2[length-1]=0
        for i in range(length-2,-1,-1):
            maxV=max(maxV,prices[i])
            f2[i]=max(f2[i+1],maxV-prices[i])
        
        res=0
        for i in range(length):
            if f1[i]+f2[i]>res: res=f1[i]+f2[i]
        return res

Run Time: 103 ms