Leetcode Link: 剑指 Offer 63. 股票的最大利润 - 力扣（LeetCode） 121. 买卖股票的最佳时机 - 力扣（LeetCode）
题目
解法一
思路： 仔细读题，本题的关键是：只能买卖一次
我们可以采用贪心的策略，遍历每一天，用一个变量保存在当前天之前的最低的价格，然后不断和获得的利润进行比较，保留最大的利润。
题解：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
res = 0
min_price = float('inf') # 迄今为止的最低价
for val in prices:
# 今天价格更低，则不卖，更新最低价格
if val < min_price: min_price = val
# 今天价格高，卖了比较利润
if val > min_price: res = max(res, val-min_price)
return res解法二
思路：动规，暴力搜索，相比较来说有点大材小用了
- 两个停止条件：1) i 到头了 2) 交易次数用尽
- 根据当前的持有状态，可以分成买/不买，卖/不卖。
题解：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# i：第i天
# stat: 持有状态，1持有，0未持有
# times：剩余交易次数，本题times最大为1
@cache
def process(i, stat, times):
if times == 0:
return 0
if i >= len(prices):
return 0
if stat == 1: # 当前持有
p1 = process(i+1, stat, times)
p2 = process(i+1, 0, 0) + prices[i]
elif stat == 0: # 当前未持有
p1 = process(i+1, stat, times)
p2 = process(i+1, 1, times) - prices[i]
return max(p1, p2)
return process(0, 0, 1)