[Leetcode] 121. Best Time to Buy and Sell Stock

Time Complexity: O(N)
Space Complexity: O(N) (Worst -> len(maxlist) = n/2

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0

        n1, n2 = 0, 1
        minlist = []
        for i in range(len(prices) - 1):
            if prices[i] < prices[n1]:
                if prices[n2] - prices[n1] > 0:
                    minlist.append(prices[n2] - prices[n1])
                n1 = i
                n2 = i + 1
            elif prices[i+1] > prices[n2]:
                n2 = i + 1
        if prices[n2] - prices[n1] > 0:
            minlist.append(prices[n2] - prices[n1])
        return max(minlist) if minlist else 0