买卖股票的最佳时机
Best Time to Buy and Sell Stock
本机进度仅保存在当前浏览器
题目描述
给定一个数组 prices，其中 prices[i] 表示某支股票第 i 天的价格。你只能选择某一天买入并在未来的某个不同的日子卖出，求所能获取的最大利润；无法获利则返回 0。
示例：prices = [7, 1, 5, 3, 6, 4]，第 2 天买入、第 5 天卖出，利润 6 - 1 = 5。
解题思路
- 遍历时维护"至今为止的最低买入价"，当天的最优卖出利润 = 当天价格 - 最低价。
- 全局答案就是各天最优卖出利润的最大值，一遍扫描完成。
- 贪心成立的直观理由：最优卖出日 j 的最佳搭档一定是 j 之前的历史最低价，拆开看每个卖出日即可独立计算。
参考实现
查看参考实现Python · 建议先自行作答
def maxProfit(prices):
# min_price 为历史最低买入价，逐日更新最大利润
min_price = float('inf')
profit = 0
for p in prices:
min_price = min(min_price, p)
profit = max(profit, p - min_price)
return profit