1. 题目
给定一个整数数组 prices，其中 prices[i] 表示第 i 天的股票价格。
你可以在每一天决定买入和/或卖出股票。任何时候你最多只能持有一支股票。但你可以在同一天买入并卖出。计算并返回你能够获得的最大利润。
2. 分析
思路
- 由于可以进行 多次交易，我们只需要每次在股票上涨的前一天买入，上涨的当天卖出。
- 这样就能把所有上涨的部分都赚到，而不亏钱。
假设股票价格走势为 [a, b, c, d]，其中：
- 如果
a → b是上涨的（b > a），那就赚取b - a。 - 如果
b → c上涨（c > b），再赚取c - b。 - 最终总利润
= (b - a) + (c - b) + ...
这样累加所有局部上升区间的利润，就能得到全局最大利润。
数学证明
- 全局最优利润 = ∑(所有上升区间的涨幅)
- 贪心策略：每次只考虑“今天比昨天贵”的情况，把所有涨价的差值加起来。
例如，prices = [1, 2, 3, 4, 5]：
- 全局最优利润：5 - 1 = 4（买在第 1 天，卖在第 5 天）
- 贪心方法的利润：
- 2 - 1 = 1
- 3 - 2 = 1
- 4 - 3 = 1
- 5 - 4 = 1
- 总和 = 4
两者结果一致，但贪心方法是每天赚取小利润，最终也是最大利润。
3. 完整代码
def maxProfit(prices):max_profit = 0for i in range(1, len(prices)):if prices[i] > prices[i-1]:max_profit += prices[i] - prices[i-1]return max_profit
print(maxProfit([7, 1, 5, 3, 6, 4]))
