找零问题实现 maxProfit 函数,计算给定价格数组的最大收益
时间: 2024-11-28 07:28:06 浏览: 22
找零问题通常涉及到动态规划或者贪心算法,其中有一个经典问题是求解股票交易中的最大收益,即通过多次买入和卖出操作来获取利润。在这个场景下,我们可以用动态规划的方式解决 maxProfit 函数的问题。假设我们有一个价格数组 `prices`,它表示每一天股票的价格,我们要找到最大的收益,可以按照以下步骤:
1. 初始化两个变量 `minPrice` 和 `maxProfit`。`minPrice` 记录到目前为止的最低价格,初始值设为数组的第一个元素;`maxProfit` 初始值设为0,用于存储最大的收益。
2. 遍历价格数组,对于每个价格 `price`:
- 如果当前价格 `price` 小于 `minPrice`,更新 `minPrice`。
- 否则,计算在当前价格卖出可以获得的利润 `profit = price - minPrice`,然后更新 `maxProfit`,取两者中的较大者,因为有可能之前的最低价比现在还低,导致更大的盈利。
3. 最终,`maxProfit` 的值就是从持有股票的角度可以获得的最大收益。
下面是伪代码示例:
```python
def maxProfit(prices):
if len(prices) < 2:
return 0
min_price = prices[0]
max_profit = 0
for price in prices[1:]:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
return max_profit
```
阅读全文