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.

public class StockProfitBruteForce {
    public static int maxProfitBruteForce(int[] prices) {
        int maxProfit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxProfit)
                    maxProfit = profit;
            }
        }
        return maxProfit;
    }
    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println("Maximum profit: " + maxProfitBruteForce(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.

public class StockProfitOptimized {
    public static int maxProfitOptimized(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int price : prices) {
            if (price < minPrice)
                minPrice = price;
            else if (price - minPrice > maxProfit)
                maxProfit = price - minPrice;
        }
        return maxProfit;
    }
    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println("Maximum profit: " + maxProfitOptimized(prices));
    }
}
            

Output:

Maximum profit: 5

Method 3: Dynamic Programming Approach

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

public class StockProfitDP {
    public static int maxProfitDP(int[] prices) {
        if (prices.length == 0) return 0;
        int[] dp = new int[prices.length];
        dp[0] = 0;
        int minPrice = prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i] = Math.max(dp[i - 1], prices[i] - minPrice);
            if (prices[i] < minPrice)
                minPrice = prices[i];
        }
        return dp[prices.length - 1];
    }
    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println("Maximum profit: " + maxProfitDP(prices));
    }
}
            

Output:

Maximum profit: 5