Best time to buy and sell stocks

Question

I'm trying my hand at the Leetcode (121. Best Time to Buy and Sell Stock) problem, and the first (brute force) way that popped to my mind was the following code.

I had thought that there wasn't any problem with the logic of the code and that the code's idea looked pretty similar to the official solution, but for some reason, my code got a Memory Limit Exceeded error. I don't want to be using a debugger since in an actual interview setting I won't be able to use one, and I want practice thinking why codes may be wrong just theoretically, but I've been having trouble doing that here. Could someone help me figure out/give me hints as to where I might be erroring?

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

My 2 cents (ok, one is not really mine)

• The first inefficiency is storing all the Profit and Loss numbers in the list, and then doing another iteration to work out the highest. Just initialize profit=0 and, every time you see an higher number in those iterations, just set profit to that number
• In any case, nested looping is another source of inefficiency here and not necessary. This is a good explanation how to avoid it.

Answer 2

try this answer

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