19 · ЛОКАЛЬНЫЙ ОПТИМУМ

Алгоритм Кадане

Лучший подмассив, заканчивающийся здесь: начать заново или продолжить предыдущий.

2 Go-примитива3 примераInterview 150

СНАЧАЛА ИНСТРУМЕНТЫ

Примитивы Go

Минимальный синтаксис, который понадобится в решении.

Состояние

current = max(value, current+value)
best = max(best, current)

Инициализируй первым элементом, чтобы обработать все отрицательные.

Границы

if value > current+value { start = i }

Дополнительные индексы восстанавливают сам диапазон.

ПРАКТИКА

Примеры решений

Три идиоматичных решения на Go с оценкой времени и памяти.

ПРИМЕР РЕШЕНИЯ

Максимальный подмассив

Отрицательный накопленный префикс выгоднее отбросить.

O(n) time · O(1) space

solution.go

func maxSubArray(nums []int) int {
    current, best := nums[0], nums[0]
    for _, n := range nums[1:] {
        current = max(n, current+n)
        best = max(best, current)
    }
    return best
}

ПРИМЕР РЕШЕНИЯ

Максимальная круговая сумма

Ответ — обычный максимум или total − минимум.

O(n) time · O(1) space

solution.go

func maxSubarraySumCircular(nums []int) int {
    total, maxEnd, maxSum := nums[0], nums[0], nums[0]
    minEnd, minSum := nums[0], nums[0]
    for _, n := range nums[1:] {
        total += n
        maxEnd = max(n, maxEnd+n); maxSum = max(maxSum, maxEnd)
        minEnd = min(n, minEnd+n); minSum = min(minSum, minEnd)
    }
    if maxSum < 0 { return maxSum }
    return max(maxSum, total-minSum)
}

ПРИМЕР РЕШЕНИЯ

Лучшая сделка

Минимальная цена прошлого играет роль лучшего отрицательного префикса.

O(n) time · O(1) space

solution.go

func maxProfit(prices []int) int {
    cheapest, profit := prices[0], 0
    for _, price := range prices[1:] {
        profit = max(profit, price-cheapest)
        cheapest = min(cheapest, price)
    }
    return profit
}

ПЕРЕД КОДОМ

Чек-лист рассуждения

Подмассив должен быть непустым?
Нужна сумма или границы
Можно ли преобразовать задачу к прибыли/разнице