题目

给定一个数组，它的第i个元素是一支给定股票第i天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。

image.png

思路

暴力法

卖出第i天所能获得的做大利润d[i]，取决于nums[i] - min(nums[j]), j <= i

创建一个dp_table，用于保存第i天卖出能获得的最大利润。

一次遍历

对于当前i卖出buy_out能获得的最大利润，只和i以前的最低买入价格buy_in有关。
使用一个变量记录最低买入价格lowest_buy_out，第i天抛出能得到的最大利润就是prices[i] - lowest_buy_out。

代码

  1. class Solution:
  2.     def maxProfit(self, prices: List[int]) -> int:
  3.         max_ans = 0
  5.         for i in range(len(prices)):
  6.             low_buy_in = prices[i]
  7.             for j in range(0, i):
  8.                 low_buy_in = min(low_buy_in, prices[j])
  9.             if prices[i] - low_buy_in > max_ans:
  10.                 max_ans = prices[i] - low_buy_in
  12.         return max_ans

空间复杂度：O(1)
时间复杂度：O(n^2)
时间复杂度超了。

  1. class Solution:
  2.     def maxProfit(self, prices: List[int]) -> int:
  3.         max_ans = 0
  4.         lowest_buy_in = float('INF')
  5.         for i in range(len(prices)):
  6.             if prices[i] < lowest_buy_in:
  7.                 lowest_buy_in = prices[i]
  8.             max_ans = max(max_ans, prices[i] - lowest_buy_in)
  10.         return max_ans

空间复杂度：O(1)
时间复杂度：O(n)