LeetCode 121 买卖股票的最佳时机 Python3

原题：链接

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例一：

示例二：

这是一道很经典的题。掌握此题及其后续一系列变种能帮助我们理解动态规划的基本套路思路。同作为"动龟"的学习者，我就不解释自己写的渣渣代码了(利用的递归思想)。代码如下：

def maxProfit(prices):
	n = len(prices)
	if n <= 1:
		return 0
	left = 0
	right = n - 1
	mid = (left + right) >> 1
	pre = maxProfit(prices[:mid+1])
	bac = maxProfit(prices[mid+1:])
	cen = max(prices[mid+1:]) - min(prices[:mid+1])
	return max(pre, bac, cen)

主要说一下下面的动态规划解法。这里参考了精选题解中不错的想法，然后自己整理一下，记录此篇，仅作为自己以后学习回顾，如看到的童鞋们觉得存在说得不对的地方，还请不吝指出，灰常感谢。

解法一

暴力法不再赘述。这里简单说说官方题解的第二种解法。
这本质上也是利用了动态规划的思想，虽然表现形式上不太相似。很明显，在买入卖出仅一次的要求下，我们只需要找到最低的买入点minPrice，及其之后最高的卖出点，保存迄今为止产生的最大利润maxprofit，并继续迭代即可。说起来简单，但实现的时候有一些需要更加细致理解的地方。

迄今为止表示的意思就是局部的最大值，也就是当前情况下我们已经获得的最大利润，并将其保存在maxprofit变量中，据此寻找全局的最大利润。为此，我们需要不断地遍历股票价格，如果出现最低的价格minPrice，我们有理由将其视为一个买入点，并在后续的过程中尝试卖出之后能否得到更大的利润。有时候，如果之后的某次交易中出现比上一个minPrice更低的买入点价格，我们同样需要重新考虑。即计算从当前开始，是否会产生比之前maxprofit更大的利润值。

举例说明一下，评论区有人说道这个序列不满足要求：
[10,2,9,1,2,1,3,1]。我们知道在第2个时间点买入2，第3个时间点卖出9，就已经得到了想要的最大利润值7。虽然之后存在更低的购入价格1，但是在之后的最大利润判断中不会出现比7更大的利润值了，尽管后续有更低价格的股票，做好判断就没啥问题！看代码吧：

def maxProfit(prices):
	# 初始化
	minPrice = float('inf')
	maxprofit = 0
	for price in prices:
		minPrice = min(minPrice, price)
		maxprofit = max(maxprofit, price - minPrice)
	return maxprofit

代码如此清爽正是动态规划的魅力所在。

解法二

精选题解中的解法：买卖股票的最佳时机 - dp 7 行简约风格
其间会涉及到一些极限和积分的简单概念。不过不懂或者不了解也完全不妨碍你能理解并掌握这种解法。

我就不写公式了，简单说来就是：

假设股票的价格服从于某种函数F，现在要求某两点函数值的差的最大值，即max(F(b)-F(a))。而求差可以转换为求其差分连续数组diff的和，动态规划很适合求解连续子数组的和：

maxprofit = max(0, diff[i] + maxprofit)

对于离散的情况，转换为求和可以这样理解(a < b 且都为整数)：

F(b) - F(a) 
= F(b) - F(b-1) + F(b-1) - F(b-2) + ... + F(b - (b-(a+1))) - F(a) 
= [F(b) - F(b-1)] + [F(b-1) - F(b-2)] + ... + [F(a+1) - F(a)] 
= diff[b-1] + diff[b-2] + ... + diff[a]

所以首先转换为差分diff数组，然后再查找其中最大的连续子数组的和。代码如下：

def maxProfit(prices):
	n = len(prices)
	diff = [0] * (n-1)
	maxprofit = 0
	# 当前最大利润
	curProfit = 0
	# 初始化 diff 数组
	for i in range(n-1):
		diff[i] = prices[i+1] - prices[i]
	# 最大连续子数组的和 ⇒ 最大利润
	for i in range(n-1):
		curProfit = max(0, diff[i] + curProfit)
		maxprofit = max(maxprofit, curProfit)
	return maxprofit

当然可以优化一下空间，将第一个循环中的diff数组拿到下面一个循环中来：

def maxProfit(prices):
	n = len(prices)
	maxprofit = 0
	# 当前最大利润
	cur = 0
	# 最大连续子数组的和 ⇒ 最大利润
	for i in range(n-1):
		cur = max(0, prices[i+1] - prices[i] + cur)
		maxprofit = max(maxprofit, cur)
	return maxprofit

解法三

纯纯的动态规划模板。其实解决此类动态规划问题的关键就是找准状态量，通过状态变换+语义理解就可以较为清晰地解题。注意本题要求：最多只允许完成一笔交易。

设动态规划数组dp[i][j]，其中i, j均为整数，0 <= i <= D, 0 <= j <= S，其中D为天数，S为持有股票的状态，0为未持有，1为持有。

现在我们赋予这个数组以意义：
dp[i][j] 表示的是第 i+1 天所处状态为 j 的最大利润值

那么我们要求解的就是最后一天、没有持有股票时候的利润最大值 dp[n-1][0](很显然其比dp[n-1][1]要大)。

其状态转移思路如下：

如果当前持有股票，只可能出现于以下2种情况：

前一天买的并没有卖掉
今天刚买的

如果当前未持有股票，同理：

今天刚卖掉
一直没有买

那么dp数组取得的最大值也就只能是这两种情形下的最大值。翻译成代码就是：

dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])

有一些边界条件：
首先是第1天的时候，很明显有dp[0][0] = 0, dp[0][1] = -prices[0]；其次因为你不能在买入股票前卖出股票，且交易仅一次。则意味着买入你目前手头的股票之前不可能有其他交易，即之前的利润值为0。

所以，代码就不难写出：

def maxProfit(prices):
	n = len(prices)
	if n == 0:
		return 0
	# dp数组初始化
	dp = [[0]*2 for _ in range(n)]
	# 初值
	dp[0][0], dp[0][1] = 0, -prices[0]
	for i in range(1, n):
		dp[i][1] = max(dp[i-1][1], -prices[i])
		dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
	return dp[n-1][0]

仔细观察可知，代码还是有优化空间复杂度的空间的。

def maxProfit(prices):
	n = len(prices)
	if n == 0:
		return 0
	# dp变量初始化
	# 初值
	dp_i_0, dp_i_1 = 0, -prices[0]
	for i in range(1, n):
		dp_i_1 = max(dp_i_1, -prices[i])
		dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])
	return dp_i_0