买卖股票的最佳时机

Question

我正在尝试解决 Leetcode（121。买卖股票的最佳时机）问题，我想到的第一个（强力）方法是以下代码。

我本来以为代码的逻辑没有任何问题，而且代码的思路看起来和官方的解决方案很相似，但是由于某种原因，我的代码出现了 Memory Limit Exceeded 错误。我不想使用调试器，因为在实际的面试环境中我无法使用调试器，并且我想练习思考为什么代码可能只是理论上错误，但我在这里一直遇到困难。有人可以帮我弄清楚/给我提示我可能在哪里出错吗？

class Solution:
def maxProfit(self, prices: List[int]) -> int:
    
    """
    brute force way:
    for every element in the list, go through every other element after that element and find their 
    differences; store all differences in a single array "profit", and find max
    """
    profit = []
    if len(prices) > 1:
        for i in range(len(prices)):
            for j in range(i+1, len(prices)):
                profit.append(prices[j] - prices[i])
    if len(profit) >= 1:     
        profitt = max(profit)
        return max(0, profitt)
    else:
        return 0

Answer 1

我的 2 美分（好吧，一分钱不是我的）

• 第一个低效之处是将所有Profit和Loss数字存储在列表中，然后进行另一次迭代以计算出最高值。只需初始化

  profit=0

  ，每次在这些迭代中看到更高的数字时，只需将

  profit

  设置为该数字
• 无论如何，嵌套循环是效率低下的另一个根源，但没有必要。 这是一个很好的解释如何避免它。

Answer 2

尝试这个答案

class Solution:
def maxProfit(self, prices: List[int]) -> int:
    curmax=0
    globalmax=0
    for i in range(1,len(prices)):
        curmax=max(curmax+(prices[i]-prices[i-1]),0)
        globalmax=max(globalmax,curmax)
    return globalmax