[Best Time to Buy and Sell Stock] Problem Set

Leetcode Dynamic Programming Problem Set (3)

  • 121.Best Time to Buy and Sell Stock
  • 122.Best Time to Buy and Sell Stock II
  • 123.Best Time to Buy and Sell Stock III
  • 188.Best Time to Buy and Sell Stock IV
  • 309.Best Time to Buy and Sell Stock with Cooldown
  • 714.Best Time to Buy and Sell Stock with Transaction Fee

There are 3 options in each trade day: buy, sell, hold
We can use a 3d array to log all situations:
dp[i][k][1 or 0] = the maximum profit at the end of the i-th day with at most k transactions and with 0 or 1 stock in our hand AFTER taking the action

1
2
3
4
5
# either always haven't got stock, or sold a stock. 
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])

# either I kept the existed stock, or bought one.
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
1
2
3
4
5
6
7
# Base case：dp[-1] means before day 0, haven't start yet.
dp[-1][k][0] = dp[i][0][0] = 0
dp[-1][k][1] = dp[i][0][1] = float('-inf')

# Recurrence relations:
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])

121. Best Time to Buy and Sell Stock

k = 1.

1
2
3
4
5
6
7
8
9
10
def maxProfit(self, prices: List[int]) -> int:
    if len(prices) < 2:
        return 0
    
    buy = prices[0]
    profit = 0
    for i in range(1, len(prices)):
        buy = min(prices[i], buy)
        profit = max(profit, prices[i] - buy)
    return profit

122. Best Time to Buy and Sell Stock II

k = inf

1
2
3
4
5
6
7
8
9
def maxProfit(self, prices: List[int]) -> int:
    last_buy = -prices[0]  # have one stock, either bought or kept
    last_sell = 0  # have no stock, either sold or kept
    for i in range(1, len(prices)):
        cur_buy = max(last_buy, last_sell - prices[i])
        cur_sell = max(last_sell, last_buy+ prices[i])
        last_buy = cur_buy
        last_sell = cur_sell
    return last_sell

123. Best Time to Buy and Sell Stock III

k = 2

1
2
3
4
5
6
7
8
9
10
def maxProfit(self, prices: List[int]) -> int:
    # last_k_numberOfStock
    gain_1_1, gain_2_1 = float('-inf'), float('-inf')
    gain_1_0, gain_2_0 = 0, 0
    for p in prices:
        gain_2_0 = max(gain_2_0, gain_2_1 + p)
        gain_2_1 = max(gain_2_1, gain_1_0 - p)
        gain_1_0 = max(gain_1_0, gain_1_1 + p)
        gain_1_1 = max(gain_1_1, -p)
    return gain_2_0

188. Best Time to Buy and Sell Stock IV

k = inf
The most general case. Very hard to understand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if len(prices) < 2 or not k:
            return 0
        
        n = len(prices)
        k = min(k, n // 2)
        
        stock0 = [0] * (k + 1)
        stock1 = [float('-inf')] * (k + 1)
        
        for price in prices:
            for j in range(k, 0, -1):
                stock0[j] = max(stock0[j], stock1[j] + price)
                stock1[j] = max(stock1[j], stock0[j-1] - price)
        return stock0[k]

309. Best Time to Buy and Sell Stock with Cooldown

k = inf + cooldown

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def maxProfit(self, prices: List[int]) -> int:
    if len(prices) < 2:
        return 0

    buy = float('-inf')
    sell = 0
    prev_sell = 0
    
    for p in prices:
        temp = sell
        sell = max(sell, buy + p)
        buy = max(buy, prev_sell - p)
        prev_sell = temp
    
    return sell

714. Best Time to Buy and Sell Stock with Transaction Fee

The same as Best Time to Buy and Sell Stock II, just need to deduct fee from profit.

1
2
3
4
5
6
7
8
9
10
11
12
def maxProfit(self, prices: List[int], fee: int) -> int:
    if len(prices) < 2:
        return 0
    
    buy = float('-inf')
    sell = 0
    
    for p in prices:
        sell = max(sell, buy + p - fee)
        buy = max(buy, sell - p)
    
    return sell

Reference