第七天——贪心算法——股票买卖问题

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 = 0
    for 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]))