LeetCode 121问题：买卖股票的最佳时机

Question

您将获得一个价格数组，其中prices[i]是给定股票在第i天的价格。

您希望通过选择某一天购买一只股票并选择未来的另一天出售该股票来最大化您的利润。

返还您可以从本次交易中获得的最大利润。如果您无法获得任何利润，请返回0。

示例：

输入：价格 = [7,1,5,3,6,4] 输出：5 解释：第 2 天买入（价格 = 1）并在第 5 天卖出（价格 = 6），利润 = 6-1 = 5。 请注意，不允许在第 2 天买入并在第 1 天卖出，因为您必须在卖出之前买入。

def maxProfit(self, prices: List[int]) -> int:
    the tests
    tempProfit = 0
    for z in range(0, len(prices)+1):
        ####if(prices[z] < prices[z+1]):###
            for x in range(z, len(prices)):
                if(prices[x] - prices[z] > tempProfit):
                    tempProfit = prices[x]-prices[z]
    return(tempProfit)

我尝试的方法是“暴力破解”所有天可能的利润并保存最高的利润。它通过了大部分测试，但 1 - 具有很长的下降值的测试 [10000,9999,9998,9997.......0] 由于运行时间长而发生（由于暴力破解） 为了解决这个问题，我尝试添加一个 if 语句，如果价格[z] > 价格[z+1]，它将避免经历第二个 for 循环。 它不起作用，因为它超出了最后一次迭代的列表长度，我如何在不超出列表长度的情况下实现这个 for 循环的逻辑？

Answer 1

对于每一天，如果买入股票，最好的卖出时间是数组中当前指数之后价格最高的那一天。因此，您可以反向迭代并维持线性解决方案迄今为止遇到的当前最大价格。

def maxProfit(self, prices: List[int]) -> int:
    max_price = max_diff = 0
    for price in reversed(prices):
        max_diff = max(max_diff, max_price - price)
        max_price = max(max_price, price)
    return max_diff