这个题用蛮力很容易做出来，既然只交易一次，那么就O（n^2）的时间复杂度，但也可以时间复杂度为O（n）的动态规划来做，分析如下：
- 状态定义：设动态规划数组dp，dp[i] 为以prices[i] 为结尾的数组的最大利润（即前i日的最大利润）。
- 转移方程：由于只交易一次，因此前i日最大利润为前i-1日的最大利润与第i天卖出的最大利润中的最大值的和：用公示表示为(dp[i] = max(dp[i−1], prices[i] − min(prices[0:i])))
- 初始状态：dp[0]=0，即首日利润为零
- 返回值：dp[n-1], n为dp列表长度
注意到min(prices[0:i]) 的时间复杂度为O（i），我们完全可以用一个变量在遍历数组的时候记录下最低的价格，用cost来表示。用于dp[i]只与dp[i-1], cost，prices[i]有关，我们用profit来表示dp[i], 因此优化了空间效率。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit, cost = 0, float("+inf")
for i in prices:
cost = min(i, cost)
profit = max(profit, i - cost)
return profit