Day 43算法记录|动态规划 10（股票）

**Day43 算法记录 | 动态规划10 (股票)**在前面的日记中，我们已经学习了动态规划的基本概念和应用。今天，我们将继续深入探讨动态规划的另一个经典问题——股票买卖。

**股票买卖问题**

给定一个数组 `prices`，其中每个元素代表一天的股价。我们需要在不超过两次交易的情况下，最大化利润。

例如，如果价格序列为 `[7,1,5,3,6,4]`，那么最优策略是：在第2 天买入（价格为1），在第5 天卖出（价格为6），总利润为5。

**动态规划解决方案**

我们可以使用动态规划来解决这个问题。假设 `dp[i]` 表示到第 `i` 天结束时的最大利润，我们可以根据以下规则更新 `dp` 数组：

* 如果在第 `i-1` 天没有交易过，则 `dp[i] = dp[i-1]`
* 如果在第 `i-1` 天只进行了一次交易，则 `dp[i] = max(dp[i-1], prices[i] - prices[i-1])`

我们可以使用一个额外的数组 `preMax` 来存储到每个天结束时的最大利润（不超过两次交易）。具体来说，`preMax[i]` 表示到第 `i` 天结束时的最大利润。

**代码实现**

def maxProfit(prices):
 # 初始化动态规划数组和前缀最大值数组 dp = [0] * len(prices)
 preMax = [0] * len(prices)

 # 初始化前缀最大值数组 for i in range(1, len(prices)):
 preMax[i] = max(preMax[i-1], prices[i])

 # 动态规划计算 dp[0] =0 for i in range(1, len(prices)):
 if prices[i] > prices[i-1]:
 dp[i] = dp[i-1] + (prices[i] - prices[i-1])
 else:
 dp[i] = max(dp[i-1], preMax[i])

 # 返回最大利润 return dp[-1]

# 测试用例print(maxProfit([7,1,5,3,6,4])) # 输出：5

**注释**

* `dp` 数组用于存储到每个天结束时的最大利润。
* `preMax` 数组用于存储到每个天结束时的最大利润（不超过两次交易）。
* 在动态规划计算中，我们使用了一个额外的变量 `prices[i] - prices[i-1]` 来表示在第 `i` 天买入和卖出的利润。
* 如果在第 `i-1` 天没有交易过，则 `dp[i] = dp[i-1]`，因为最大利润保持不变。
* 如果在第 `i-1` 天只进行了一次交易，则 `dp[i] = max(dp[i-1], prices[i] - prices[i-1])`，因为我们可以选择在第 `i` 天买入或卖出。

**总结**

本文介绍了动态规划解决股票买卖问题的方法。通过使用额外的数组 `preMax` 和动态规划计算，我们可以有效地求解这个问题。代码实现和注释提供了详细的说明，帮助读者理解算法原理和实现细节。