Buy and sell stock

Code Pattern

Base Case

n: Number of price points. Adjust k based on whether transactions are unlimited.
if k >= n // 2: checks if the number of allowed transactions (k) is at least half the number of price points (n). This means the trader can effectively buy and sell freely.
sum(max(0, prices[i] - prices[i - 1]) for i in range(1, n)) calculates total profit:
- prices[i] - prices[i - 1]: Computes daily price changes.
- max(0, ...): Ensures only positive changes (profits) are counted.
- sum(...): Adds up all the profitable changes.

Dynamic Programming

dp[k][0] represents maximum profit at k transactions without holding stock
dp[k][1] represents maximum profit at k transactions while holding stock

Union function

dp[j][0] = max(dp[j][0], dp[j][1] + price) updates the maximum profit when not holding stock (either stay in that state or sell stock).
dp[j][1] = max(dp[j][1], dp[j-1][0] - price) updates the maximum profit while holding stock (either stay in that state or buy stock).

def BasicProfit(self, k: int, prices: List[int], max_txn: int = float('inf')) -> int:
    """
    Universal solution for all stock trading problems
    k: number of transactions allowed (use float('inf') for unlimited)
    prices: list of stock prices
    max_txn: maximum number of transactions allowed
    """

    n = len(prices)
    k = min(k, n//2) if max_txn == float('inf') else max_txn
    
    # For unlimited transactions, use greedy approach
    if k >= n//2:
        return sum(max(0, prices[i] - prices[i-1]) for i in range(1, n))

Common mistakes

Wrong DP Array Initialization

# Wrong: using 0 instead of -inf
dp = [[0] * 2 for _ in range(k + 1)]  # Can't track losses properly
# Wrong: forgetting to set initial state
dp = [[-float('inf')] * 2 for _ in range(k + 1)]  # Forgot dp[0][0] = 0
# Correct:
dp = [[-float('inf')] * 2 for _ in range(k + 1)]
dp[0][0] = 0  # Initial state with no transactions

Incorrect Return Value

# Wrong: not handling negative profits
return dp[k][0]  # Doesn't handle case where no transaction is better
# Wrong: forgetting to check all transaction counts
return max(dp[k][0], 0)  # Might miss better profit with fewer transactions
# Correct:
return max(0, max(dp[i][0] for i in range(k + 1)))

Issues and consideration

121. Best Time to Buy and Sell Stock

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return self.BasicProfit(1, prices, 1)

122. Best Time to Buy and Sell Stock II

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return self.BasicProfit(float('inf'), prices)

123. Best Time to Buy and Sell Stock III

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return self.BasicProfit(2, prices, 2)

188. Best Time to Buy and Sell Stock IV

class Solution:
    def maxProfit(self, k, prices: List[int]) -> int:
        return self.BasicProfit(k, prices, k)

Buy and sell stock

Code Pattern

Base Case

Dynamic Programming

Union function

Common mistakes

Issues and consideration

Related Problem