LeetCode 买卖股票最佳时机含手续费题解

LeetCode 买卖股票最佳时机含手续费题解

题目描述

给定一个整数数组 prices，其中第 i 个元素表示第 i 天的股票价格。设计一个算法计算出最大利润。你可以无限次地完成交易，但是每次交易都需要手续费。

示例：

输入：prices = [1, 3, 2, 8, 4, 9],fee = 2
输出：8

解题思路

方法：动态规划

思路：

• 使用动态规划，维护两种状态：持有现金和持有股票。
• 持有现金：之前就已经不持有股票，或者今天卖出了股票。
• 持有股票：之前就持有股票，或者今天买入了股票。

复杂度分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

代码实现

def max_profit(prices, fee): cash = 0 hold = -prices[0] for i in range(1, len(prices)): cash = max(cash, hold + prices[i] - fee) hold = max(hold, cash - prices[i]) return cash # 测试 def test_max_profit(): prices = [1, 3, 2, 8, 4, 9] fee = 2 print(max_profit(prices, fee)) # 输出：8 if __name__ == "__main__": test_max_profit()

总结

买卖股票最佳时机含手续费是动态规划的典型应用，通过维护持有现金和持有股票两种状态来计算最大利润。