算法-股票买卖问题

def maxProfit(prices):
    if not prices:
        return 0
    
    min_price = float('inf')
    max_profit = 0
    
    for price in prices:
        # 更新最低买入价
        min_price = min(min_price, price)
        # 计算当前最大利润
        max_profit = max(max_profit, price - min_price)
    
    return max_profit

def maxProfit(prices):
    profit = 0
    for i in range(1, len(prices)):
        # 只要存在利润就交易
        if prices[i] > prices[i-1]:
            profit += prices[i] - prices[i-1]
    
    return profit

def maxProfit(prices):
    if len(prices) < 2:
        return 0
    
    # dp[i][0]: 不持有股票且不在冷却期的最大利润
    # dp[i][1]: 不持有股票且在冷却期的最大利润
    # dp[i][2]: 持有股票的最大利润
    dp = [[0, 0, 0] for _ in range(len(prices))]
    
    # 初始状态
    dp[0][2] = -prices[0]
    
    for i in range(1, len(prices)):
        # 不持有股票且不在冷却期：可以是前一天就不持有，或者今天卖出股票
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])
        
        # 不持有股票且在冷却期：必须是今天卖出股票
        dp[i][1] = dp[i-1][2] + prices[i]
        
        # 持有股票：可以是前一天就持有，或者今天买入股票
        dp[i][2] = max(dp[i-1][2], dp[i-1][0] - prices[i])
    
    # 最后返回不持有股票的最大利润
    return max(dp[-1][0], dp[-1][1])

def maxProfit(k, prices):
    if not prices or k == 0:
        return 0
    
    # 如果k很大，相当于可以无限次交易
    if k >= len(prices) // 2:
        return sum(max(0, prices[i] - prices[i-1]) for i in range(1, len(prices)))
    
    # dp[i][j][0]: 第i天，已进行j次交易，当前不持有股票的最大利润
    # dp[i][j][1]: 第i天，已进行j次交易，当前持有股票的最大利润
    dp = [[[0, float('-inf')] for _ in range(k + 1)] for _ in range(len(prices))]
    
    # 初始状态
    for j in range(k + 1):
        dp[0][j][1] = -prices[0]
    
    for i in range(1, len(prices)):
        for j in range(1, k + 1):
            # 不持有股票：要么前一天就不持有，要么今天卖出
            dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
            
            # 持有股票：要么前一天就持有，要么今天买入
            dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])
    
    # 返回最后不持有股票的最大利润
    return max(dp[-1][j][0] for j in range(k + 1))

def maxProfit(prices, fee):
    if len(prices) < 2:
        return 0
    
    # dp[i][0]: 不持有股票的最大利润
    # dp[i][1]: 持有股票的最大利润
    dp = [[0, 0] for _ in range(len(prices))]
    
    # 初始状态
    dp[0][1] = -prices[0]
    
    for i in range(1, len(prices)):
        # 不持有股票：要么前一天就不持有，要么今天卖出股票（扣除手续费）
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)
        
        # 持有股票：要么前一天就持有，要么今天买入股票
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
    
    # 返回最后不持有股票的最大利润
    return dp[-1][0]