LeetCode 最大收益题解

LeetCode 最大收益题解题目描述给定一个数组 prices其中 prices[i] 是第 i 天的股票价格。计算能够获得的最大利润。示例输入prices [7,1,5,3,6,4]输出7解题思路方法动态规划思路使用动态规划dp[i] 表示第 i 天能够获得的最大利润。dp[i] max(dp[i-1] prices[i] - prices[i-1], prices[i] - prices[i-1])。复杂度分析时间复杂度O(n)。空间复杂度O(1)。代码实现def max_profit(prices): if not prices: return 0 profit 0 for i in range(1, len(prices)): profit max(0, prices[i] - prices[i-1]) return profit # 测试 def test_max_profit(): prices [7, 1, 5, 3, 6, 4] print(max_profit(prices)) # 输出7 if __name__ __main__: test_max_profit()总结最大收益是动态规划的典型应用通过累加每天的正利润来计算最大收益。