Поиск максимальной прибыли от акций

Поиск максимальной прибыли от акций

Это одна из самых популярных задач на собеседованиях. Ее красота в простоте подхода и эффективности: одиночный проход по массиву дает оптимальное решение.

Решение 1: Однопроходный алгоритм — O(n) время, O(1) пространство

Основная идея: отслеживаем минимальную цену, встреченную до текущего момента, и вычисляем прибыль для текущей цены.

public class MaxProfitStock {
    /**
     * Найти максимальную прибыль от покупки и продажи акции
     * Время: O(n)
     * Пространство: O(1)
     */
    public static int maxProfit(int[] prices) {
        // Обработка пустого массива
        if (prices == null || prices.length < 2) {
            return 0;  // нельзя купить и продать
        }
        
        int minPrice = prices[0];  // минимальная цена, встреченная до текущего дня
        int maxProfit = 0;         // максимальная прибыль
        
        // Проходим по всем ценам начиная со второго дня
        for (int i = 1; i < prices.length; i++) {
            int currentPrice = prices[i];
            
            // Вычисляем прибыль, если продадим сегодня
            int profit = currentPrice - minPrice;
            
            // Обновляем максимальную прибыль
            maxProfit = Math.max(maxProfit, profit);
            
            // Обновляем минимальную цену
            minPrice = Math.min(minPrice, currentPrice);
        }
        
        return maxProfit;
    }
    
    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4}));  // 5
        System.out.println(maxProfit(new int[]{7, 6, 4, 3, 1}));     // 0
        System.out.println(maxProfit(new int[]{2, 4, 1}));           // 2
        System.out.println(maxProfit(new int[]{1}));                 // 0
        System.out.println(maxProfit(new int[]{2, 1, 2, 0, 1}));     // 1
    }
}

Как это работает для [7, 1, 5, 3, 6, 4]:

Е0: price=7, minPrice=7, profit=0, maxProfit=0
Е1: price=1, minPrice=1, profit=1-1=0, maxProfit=0
Е2: price=5, minPrice=1, profit=5-1=4, maxProfit=4
Е3: price=3, minPrice=1, profit=3-1=2, maxProfit=4
Е4: price=6, minPrice=1, profit=6-1=5, maxProfit=5 ✓
Е5: price=4, minPrice=1, profit=4-1=3, maxProfit=5

Ответ: 5 (купить за 1, продать за 6)

Решение 2: С дополнительной валидацией и логированием

public class MaxProfitStockDetailed {
    /**
     * Версия с возвращением информации о покупке и продаже
     */
    static class Transaction {
        int buyPrice;
        int sellPrice;
        int profit;
        
        Transaction(int buyPrice, int sellPrice) {
            this.buyPrice = buyPrice;
            this.sellPrice = sellPrice;
            this.profit = sellPrice - buyPrice;
        }
        
        @Override
        public String toString() {
            return String.format("Купить за %d, продать за %d, прибыль: %d", 
                    buyPrice, sellPrice, profit);
        }
    }
    
    /**
     * Найти максимальную прибыль и деньги транзакции
     */
    public static Transaction findMaxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return new Transaction(0, 0);
        }
        
        int minPrice = prices[0];
        int maxProfit = 0;
        int buyPrice = prices[0];
        int sellPrice = prices[0];
        
        for (int i = 1; i < prices.length; i++) {
            int currentPrice = prices[i];
            int profit = currentPrice - minPrice;
            
            if (profit > maxProfit) {
                maxProfit = profit;
                buyPrice = minPrice;
                sellPrice = currentPrice;
            }
            
            minPrice = Math.min(minPrice, currentPrice);
        }
        
        return new Transaction(buyPrice, sellPrice);
    }
    
    public static void main(String[] args) {
        System.out.println(findMaxProfit(new int[]{7, 1, 5, 3, 6, 4}));
        // Купить за 1, продать за 6, прибыль: 5
        
        System.out.println(findMaxProfit(new int[]{7, 6, 4, 3, 1}));
        // Купить за 7, продать за 7, прибыль: 0
    }
}

Решение 3: С индексами дней покупки и продажи

public class MaxProfitWithDays {
    /**
     * Возвращает индексы дней покупки и продажи для максимальной прибыли
     */
    public static int[] findMaxProfitDays(int[] prices) {
        if (prices == null || prices.length < 2) {
            return new int[]{-1, -1};
        }
        
        int minPrice = prices[0];
        int minPriceDay = 0;     // день с минимальной ценой
        int maxProfit = 0;
        int buyDay = 0;          // день покупки
        int sellDay = 0;         // день продажи
        
        for (int i = 1; i < prices.length; i++) {
            int profit = prices[i] - minPrice;
            
            if (profit > maxProfit) {
                maxProfit = profit;
                buyDay = minPriceDay;
                sellDay = i;
            }
            
            if (prices[i] < minPrice) {
                minPrice = prices[i];
                minPriceDay = i;
            }
        }
        
        return new int[]{buyDay, sellDay};
    }
    
    public static void main(String[] args) {
        int[] result = findMaxProfitDays(new int[]{7, 1, 5, 3, 6, 4});
        System.out.println(String.format("Купить в день %d, продать в день %d", 
                result[0], result[1]));
        // Купить в день 1, продать в день 4
    }
}

Решение 4: С обработкой множественных транзакций (усложнение)

Если бы нужно было несколько покупок и продаж:

public class MaxProfitMultiple {
    /**
     * Максимальная прибыль с несколькими покупками и продажами
     */
    public static int maxProfitMultiple(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        
        int maxProfit = 0;
        
        // Покупаем перед каждым повышением цены
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        
        return maxProfit;
    }
    
    public static void main(String[] args) {
        System.out.println(maxProfitMultiple(new int[]{7, 1, 5, 3, 6, 4}));
        // 7 (1->5 = 4, 3->6 = 3, всего = 7)
    }
}

Визуализация для [7, 1, 5, 3, 6, 4]

Цены:        7 1 5 3 6 4
            \ | | | | |
             \+3+1+2+3+1

Мин цена:   7 1 1 1 1 1
Прибыль:    0 0 4 2 5 3
Макс:       0 0 4 4 5 5

Оптимально: купить за 1 (день 1), продать за 6 (день 4)

Почему этот алгоритм работает

1. Минимальная цена слева — это лучшая цена для покупки до текущего дня
2. Текущая цена минус минимум — это прибыль если продать сегодня
3. Отслеживание максимума — найдем лучшую пару для покупки-продажи
4. Один проход — достаточно проойти массив один раз, не нужны вложенные циклы

Сложность

На собеседовании

1. Подумайте вслух перед кодированием
2. Объясните подход: отслеживать минимум и вычислять прибыль
3. Реализуйте базовое решение за 5 минут
4. Проверьте граничные случаи: пустой массив, один элемент
5. Тестируйте на примерах из условия
6. Упомяните усложнения: множественные транзакции, временные окна

Граничные случаи

• Пустой массив или null → 0
• Один элемент → 0
• Цены только падают → 0
• Цены только растут → максимум различия
• Все одинаковые → 0