前往此题

遍历法

这题是股票类问题中最简单的一道题，可以通过一次遍历法来解决。

1. 创建变量minPrice，用于记录最小买入价格
2. 创建变量maxprofit，用于记录最大的差值

在遍历的时候我们一边记录最小买入价格minPrice，于此同时还需要计算最大差值price（当前价格） - minPrice

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minPrice = float('inf')
        maxprofit = 0

        for p in prices:
            minPrice = min(minPrice, p)
            maxprofit = max(maxprofit, p - minPrice)
        return maxprofit

动态规划

动态规划做题步骤

1. dp[i]应该表示什么
2. 根据dp[i]和dp[i-1]的关系得出状态转移方程
3. 确定初始条件dp[0]

• dp[i]表示的是第i天的最大利润
• 状态转移方程:dp[i] = max(dp[i-1], prices[i] - minPrice)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        N = len(prices)
        if N == 0: return 0
        dp = [0] * N
        minPrice = prices[0]

        for i in range(1, N):
            minPrice = min(minPrice, prices[i])
            dp[i] = max(dp[i-1], prices[i] - minPrice)
        return dp[-1]