原题地址

image.png

思路

这道题需要求价格最低的一天买进，价格最高的一天卖出，隐含条件就是 买进后才能卖出 。

  1. 假设数组长度为 n ，则买进有 n 种可能，卖出也有 n 种可能，由此便得到了 暴力求解 算法。

暴力求解 无非就是两重循环，这里不再赘述。

  1. 暴力求解没有用到隐含条件，如果加入隐含条件，我们又能得到什么算法呢？我们借助 动态规划 的思路来想，如果第 i 天卖出，我们设 dp[i] 为第 i 天卖出所获得的利润，则可以得到公式

dp[i] = prices[i] - min_price (if prices[i] > min_price)
dp[i] = 0 (if prices[i] <= min_price)
因为买进后才能卖出，所以 min_price 为第 i 天之前的价格最小值。

  1. 这样我们就可以通过 一次循环 求出每一天卖出所获得的利润，同时用一个变量来记录最大利润。

注：本题也可以采取从后向前遍历，通过求第 i 天买进的利润，来得到最大利润，思路完全一致，不再给出代码。

python代码

  1. def maxProfit(self, prices: List[int]) -> int:
  2.     n = len(prices)
  3.     if n < 2:
  4.         return 0
  5.     min_price, min_index = prices[0], 0
  6.     max_profit = 0
  7.     for i in range(1, n):  # 循环求出第i天卖出所获得的利润
  8.         if prices[i] > min_price:   #当天价格高，可以卖出，更新最大利润
  9.             max_profit = max(max_profit, prices[i]-min_price)
  10.         else:   # 当天价格低，不能卖，所以不需要更新最大利润。更新最小价格
  11.             min_price = prices[i]
  12.             min_index = i
  13.     return max_profit

时空复杂度

时间复杂度O(N)

空间复杂度O(1)