# You are given an array prices where prices[i] is the price of a given stock on the ith day.

# You want to maximize your profit by choosing a single day to buy one stock and choosing a different
# day in the future to sell that stock.

# Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit,
# return 0.

# Example 1:
#   Input: prices = [7,1,5,3,6,4]
#   Output: 5
# Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
# Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

# Example 2:
#   Input: prices = [7,6,4,3,1]
#   Output: 0
# Explanation: In this case, no transactions are done and the max profit = 0.

# 1 <= prices.length <= 10^5
# 0 <= prices[i] <= 10^4

from typing import List


class InitialSolution:
    def maxProfit(self, prices: List[int]) -> int:
        max_price, min_price_idx, max_price_idx = 0, 0, 0

        for idx in range(len(prices)):
            if prices[idx] > prices[max_price_idx]:
                max_price_idx = idx
            if prices[idx] < prices[min_price_idx]:
                min_price_idx = idx
                max_price_idx = idx
            max_price = max(max_price, prices[max_price_idx] - prices[min_price_idx])

        if max_price <= 0:
            return 0

        return max_price


class MinMaxSolution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price, max_profit = float('inf'), 0
        for price in prices:
            min_price = min(min_price, price)
            max_profit = max(max_profit, price - min_price)

        return max_profit


class TwoPointersSolution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit, buy, sell = 0, 0, 1
        while sell < len(prices):
            if prices[buy] < prices[sell]:
                profit = prices[sell] - prices[buy]
                max_profit = max(max_profit, profit)
            else:
                buy = sell
            sell += 1

        return max_profit

# You are given an array prices where prices[i] is the price of a given stock on the ith day.

# You want to maximize your profit by choosing a single day to buy one stock and choosing a different
# day in the future to sell that stock.

# Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit,
# return 0.

# Example 1:
#   Input: prices = [7,1,5,3,6,4]
#   Output: 5
# Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
# Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

# Example 2:
#   Input: prices = [7,6,4,3,1]
#   Output: 0
# Explanation: In this case, no transactions are done and the max profit = 0.

# 1 <= prices.length <= 10^5
# 0 <= prices[i] <= 10^4

from typing import List


class InitialSolution:
    def maxProfit(self, prices: List[int]) -> int:
        max_price, min_price_idx, max_price_idx = 0, 0, 0

        for idx in range(len(prices)):
            if prices[idx] > prices[max_price_idx]:
                max_price_idx = idx
            if prices[idx] < prices[min_price_idx]:
                min_price_idx = idx
                max_price_idx = idx
            max_price = max(max_price, prices[max_price_idx] - prices[min_price_idx])

        if max_price <= 0:
            return 0

        return max_price


class MinMaxSolution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price, max_profit = float('inf'), 0
        for price in prices:
            min_price = min(min_price, price)
            max_profit = max(max_profit, price - min_price)

        return max_profit


class TwoPointersSolution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit, buy, sell = 0, 0, 1
        while sell < len(prices):
            if prices[buy] < prices[sell]:
                profit = prices[sell] - prices[buy]
                max_profit = max(max_profit, profit)
            else:
                buy = sell
            sell += 1

        return max_profit

# You are given an array prices where prices[i] is the price of a given stock on the ith day. # You want to maximize your profit by choosing a single day to buy one stock and choosing a different # day in the future to sell that stock. # Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, # return 0. # Example 1: #   Input: prices = [7,1,5,3,6,4] #   Output: 5 # Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. # Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell. # Example 2: #   Input: prices = [7,6,4,3,1] #   Output: 0 # Explanation: In this case, no transactions are done and the max profit = 0. # 1 <= prices.length <= 10^5 # 0 <= prices[i] <= 10^4