Best Time to Buy and Sell Stock

Условие

Дан массив целых чисел prices, где prices[i] — это цена акции в день i. Вам нужно выбрать один день для покупки акции и другой день в будущем для продажи, чтобы получить максимальную прибыль. Верните максимальную прибыль, которую можно получить от одной транзакции. Если прибыль получить невозможно, верните 0.

Примеры

Input: prices = [7, 1, 5, 3, 6, 4]

Output: 5

Explanation: Купите на 2-й день (цена = 1) и продайте на 5-й день (цена = 6), прибыль = 6-1 = 5.

Input: prices = [7, 6, 4, 3, 1]

Output: 0

Explanation: Прибыль невозможна, поскольку цены только падают.

Решение

fun maxProfit(prices: IntArray): Int {
    if (prices.isEmpty()) return 0
    
    var minPrice = Int.MAX_VALUE  // Инициализируем минимальную цену очень большим числом
    var maxProfit = 0  // Инициализируем максимальную прибыль
    
    for (price in prices) {
        // Обновляем минимальную цену, если текущая цена меньше
        if (price < minPrice) {
            minPrice = price
        } else {
            // Вычисляем прибыль и обновляем максимальную прибыль
            val profit = price - minPrice
            if (profit > maxProfit) {
                maxProfit = profit
            }
        }
    }
    
    return maxProfit
}

Временная сложность

O(n), где n — количество дней. Проходим по массиву один раз, обновляя минимальную цену и максимальную прибыль.

Пространственная сложность

O(1), так как используем только несколько переменных для хранения промежуточных значений.