121.买卖股票的最佳时机.md

121. 买卖股票的最佳时机

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

解法一：暴力

双重循环，i表示买入日期，j表示卖出日期，遍历所有组合。（超时）

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        maxP = 0    #初始为0
        for i in range(len(prices)):
            for j in range(i+1, len(prices)):
                maxP = max(maxP, prices[j] - prices[i])    #求最大利润
        return maxP

解法二：一次遍历

每次先更新最低价格，然后用当前价格减最低价格得到当前利润，并更新最高利润

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price, max_profit = sys.maxsize, 0
        #一次遍历，从前往后，每次更新最小值，用当前价格减去最小值计算差价，遇到最大价格则更新
        for i in range(len(prices)):
            min_price = min(min_price, prices[i])
            max_profit = max(max_profit, prices[i] - min_price)
        return max_profit

解法三：状态机dp

即k=1，直接套状态转移方程，根据 base case，可以做一些化简：

1 ≤ i < n
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i]) 
            = max(dp[i-1][1][1], -prices[i])  #解释：k = 0 的 base case，所以 dp[i-1][0][0] = 0。

现在发现 k 都是 1，不会改变，即 k 对状态转移已经没有影响了。 可以进行进一步化简去掉所有 k：

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

边界条件：

dp[0][0] = 0
dp[0][1] = -∞

容易出代码

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n == 0:
            return 0
        dp = [[0] *2 for _ in range(n+1)]
        #用i=0表示初始条件，即i=1为第1天
        for i in range(n+1):
            if i == 0:
                dp[i][0] = 0
                dp[i][1] = -sys.maxsize
                continue
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1])
            dp[i][1] = max(dp[i-1][1], -prices[i-1])
        return dp[n][0]