✏️ Как заработать на всех взлётах цены акций

Дан массив цен акций по дням. Нужно найти максимальную прибыль, совершая любое количество сделок купли-продажи. Одновременно можно держать только одну акцию.

Пример:

Цены: [7, 1, 5, 3, 6, 4]
Ответ: 7

Покупаем за 1, продаём за 5 (прибыль 4). Покупаем за 3, продаём за 6 (прибыль 3). Итого — 7.

Алгоритм

Самый простой подход — жадный алгоритм. Если завтра цена выше, чем сегодня — покупаем сегодня и продаём завтра. Собираем прибыль с каждого роста цены.

Представьте график цен: вам нужно получить прибыль со всех участков, где график идёт вверх. Неважно, сколько это будет сделок — каждый рост приносит деньги.

Почему это работает

Если цена растёт три дня подряд (например, 1 → 3 → 5), то неважно, продавать ли каждый день или держать до конца.

Код:

public class Solution 
{
    public int MaxProfit(int[] prices) 
    {
        if (prices == null || prices.Length < 2)
            return 0;
        
        int totalProfit = 0;
        
        for (int i = 1; i < prices.Length; i++)
        {
            // Если цена выросла — берём эту прибыль
            if (prices[i] > prices[i - 1])
            {
                totalProfit += prices[i] - prices[i - 1];
            }
        }
        
        return totalProfit;
    }
}

Или ещё компактнее:

public class Solution 
{
    public int MaxProfit(int[] prices) 
    {
        int profit = 0;
        
        for (int i = 1; i < prices.Length; i++)
        {
            profit += Math.Max(0, prices[i] - prices[i - 1]);
        }
        
        return profit;
    }
}

Жадный подход здесь безупречен: захватываем каждый рост, игнорируем падения. Никаких сложных расчётов оптимальных точек — только простая логика и максимальная прибыль.

➡️ Попробовать решить

Чтобы щёлкать такие задачи нужно знать алгоритмы. Подтянуть такую базу поможет наш курс по алгоритмам. До конца октября скидка 40%

🐸 Библиотека шарписта

#dotnet_challenge