# Function to calculate the maximum profit from a list of stock prices
# where you are allowed to make only one buy and one sell transaction.
# You must buy before you sell.
def max_profit(prices: List[UInt]) -> UInt:
var max_profit: UInt = 0 # Stores the maximum profit found so far
buy_day = 0 # Pointer to track the day to buy the stock
sell_day = 1 # Pointer to track the day to sell the stock
# Loop until sell_day reaches the end of the price list
while sell_day < len(prices):
if prices[buy_day] < prices[sell_day]:
# If selling is profitable, calculate profit and update max
max_profit = max(max_profit, prices[sell_day] - prices[buy_day])
else:
# If current sell_day is cheaper than buy_day, shift buy_day
buy_day = sell_day
sell_day += 1 # Move to the next day
return max_profit # Return the highest profit found
def main():
# First test: Best profit is buying at 1 and selling at 6 => profit = 5
prices = [7, 1, 5, 3, 6, 4]
debug_assert(max_profit(prices) == 5, "Assertion failed")
# Second test: No profitable day to sell => profit = 0
prices = [7, 6, 4, 3, 1]
debug_assert(max_profit(prices) == 0, "Assertion failed")