Best Time to Buy and Sell Stock

  # 🟩 Best Time to Buy and Sell Stock
  #
  # Input Examples:
  #   max_profit([7, 1, 5, 3, 6, 4]) => 5  # Buy at 1, sell at 6
  #   max_profit([7, 6, 4, 3, 1]) => 0     # No profit possible
  #
  # Time Complexity: O(n)
  def max_profit(prices)
    min_price = Float::INFINITY
    max_profit = 0

    prices.each_with_index do |price, i|
      if price < min_price
        min_price = price
        puts "Day #{i}: New min price = #{min_price}"
      else
        profit = price - min_price
        max_profit = [ max_profit, profit ].max
        puts "Day #{i}: Current price = #{price}, Profit if sold = #{profit}, Max Profit = #{max_profit}"
      end
    end

    puts "Final max profit: #{max_profit}"
    max_profit