Best Time to Buy and Sell Stock

Understanding the Problem

The goal is to determine the maximum profit that can be achieved by buying and selling a stock at most once.

Method 1: Brute Force Approach

This method checks all possible pairs of buy and sell prices to find the maximum profit.

def max_profit_brute_force(prices):
    max_profit = 0
    for i in range(len(prices) - 1):
        for j in range(i + 1, len(prices)):
            profit = prices[j] - prices[i]
            if profit > max_profit:
                max_profit = profit
    return max_profit

prices = [7, 1, 5, 3, 6, 4]
print("Maximum profit:", max_profit_brute_force(prices))
            

Output:

Maximum profit: 5

Method 2: Optimized Approach

This method uses a single pass through the array to track the minimum price and maximum profit.

def max_profit_optimized(prices):
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_profit:
            max_profit = price - min_price
    return max_profit

prices = [7, 1, 5, 3, 6, 4]
print("Maximum profit:", max_profit_optimized(prices))
            

Output:

Maximum profit: 5

Method 3: Dynamic Programming Approach

This method keeps track of minimum prices and calculates profit dynamically.

def max_profit_dp(prices):
    if not prices:
        return 0
    dp = [0] * len(prices)
    min_price = prices[0]
    for i in range(1, len(prices)):
        dp[i] = max(dp[i - 1], prices[i] - min_price)
        if prices[i] < min_price:
            min_price = prices[i]
    return dp[-1]

prices = [7, 1, 5, 3, 6, 4]
print("Maximum profit:", max_profit_dp(prices))
            

Output:

Maximum profit: 5