121. Best Time to Buy and Sell Stock

# Approach 1. Brute Force
# Time Complexity: O(n^2)
# Space Complexity: O(1)
class Solution1:
    def maxProfit(self, prices):
        max_profit = 0
        for i in range(len(prices)):
            for j in range(i + 1, len(prices)):
                profit = prices[j] - prices[i]
                if profit > max_profit:
                    max_profit = profit
        return max_profit


# Approach 2. One loop
# Time Complexity: O(n)
# Space Complexity: O(1)
class Solution2:
    def maxProfit(self, prices):
        max_profit = 0
        for i in range(len(prices)):
            for j in range(i + 1, len(prices)):
                profit = prices[j] - prices[i]
                if profit > max_profit:
                    max_profit = profit
        return max_profit