[Leetcode]188. Best Time to Buy and Sell Stock IV

This series of Buy and Sell Stock I~VI on Leetcode is a great practice for Dynamic Programming – State Machine. Therefore I prepared blogs for each of them and hopefully it would help you to understand them better. You can find the relations of them at the bottom and feel free to leave any comments.

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 k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Dynamic programming 1 – State Machine

Based on [Leetcode]122. Best Time to Buy and Sell Stock II, we now have one more constraint: we can have only k transactions at most. In this case, a two-dimensional array won’t cover all dimensions including day i, cash/hold, transaction k. Therefore we need a three-dimensional array so that:

dp[i,k,0] means the largest profit we can make on day i with k transactions and no stock in hands (cash).
dp[i,k,1] means the largest profit we can make on day i with k transactions and 1 stock in hands (hold).

Therefore the transition function is easy to define:

dp[i,k,0] = max(dp[i-1,k,0],dp[i-1][k][1]+prices[i])
dp[i,k,1] = max(dp[i-1,k,1],dp[i-1][k-1][0]-prices[i])

Notice that we only count buy as the transactions. Besides, we need to set up the initializations:

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0
        if k < 1:
            return 0
        # when k is large enough, take greedy
        if k >= len(prices)//2:
            ret = 0
            for i in range(1,len(prices)):
                ret += max(0,prices[i]-prices[i-1])
            return ret
        
        dp = [[[0 for _ in range(2)] for _ in range(k+1)] for _ in range(len(prices))] # [[[cash,hold]]]
        for i in range(len(prices)):
            dp[i][0][0] = 0
            dp[i][0][1] = float('-inf')
        for kk in range(1,k+1):
            dp[0][kk][1] = -prices[0]
        
        for i in range(1,len(prices)):
            for kk in range(1,k+1):
                dp[i][kk][0] = max(dp[i-1][kk][0],dp[i-1][kk][1]+prices[i])
                dp[i][kk][1] = max(dp[i-1][kk][1],dp[i-1][kk-1][0]-prices[i])
        return max(dp[-1][e][0] for e in range(1,k+1))

Dynamic programming 2

Another way of using dynamic programming is to define dp[i,k] as the largest profit we could make on day i with transaction k. Therefore the transition function is:

Apparently we would need a inner iteration for j. And this would lead to $O(n^2k)$ time complexity, $O(nk)$ space complexity and TLE.

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0
        dp = [[0 for _ in range(k+1)] for _ in range(len(prices))]      
        for i in range(1,len(prices)):
            for kk in range(1,k+1):
                high = prices[i] - prices[0]
                for j in range(1,i+1):
                    high = max(high,prices[i]-prices[j]+dp[j-1][kk-1])
                dp[i][kk] = max(dp[i-1][kk],high)
        return dp[-1][-1]

With a small tweak of the function, instead of looking for max(prices[i]-prices[j]+dp[j-1,k-1]), we can look for min(prices[j]-dp[j-1,k-1]), so that we can store this value along with the outer iteration, reducing the time complexity to $O(nk)$ .

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0
        if k >= len(prices)//2:
            ret = 0
            for i in range(1,len(prices)):
                ret += max(0,prices[i]-prices[i-1])
            return ret
        dp = [[0 for _ in range(k+1)] for _ in range(len(prices))]      
        low = [prices[0] for _ in range(k+1)]
        for i in range(1,len(prices)):
            for kk in range(1,k+1):
                low[kk] = min(low[kk],prices[i]-dp[i-1][kk-1])
                dp[i][kk] = max(dp[i-1][kk],prices[i]-low[kk])
        return dp[-1][-1]

Furthermore, if we swap the order of two iterations, i.e.:

for kk in range(1,k+1):        
	for i in range(1,len(prices)):

Then we found dp[i,k] and low[i,k] only rely on dp[i-1,k] and low[i-1,k], therefore we could reduce the space complexity to $O(k)$ with time complexity being O(nk)[/latex[.

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0
        # when k is large enough, take greedy
        if k >= len(prices)//2:
            ret = 0
            for i in range(1,len(prices)):
                ret += max(0,prices[i]-prices[i-1])
            return ret
        dp = [0] * (k+1)
        low = [prices[0]] * (k+1)
        for i in range(1,len(prices)):
            for kk in range(1,k+1):
                low[kk] = min(low[kk],prices[i]-dp[kk-1])
                dp[kk] = max(dp[kk],prices[i]-low[kk])
        return dp[-1]

Relations

Reference

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/135704/Detail-explanation-of-DP-solution
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/Most-consistent-ways-of-dealing-with-the-series-of-stock-problems

Dynamic programming 1 – State Machine

Dynamic programming 2

Relations

Reference

Related posts: