Как обрабатывать последовательность за один проход и постоянную память?

Линейная потоковая обработка читает каждый элемент один раз и хранит только агрегированное состояние. Такой метод нужен, когда последовательность велика или поступает по сети и…

Линейная потоковая обработка читает каждый элемент один раз и хранит только агрегированное состояние. Такой метод нужен, когда последовательность велика или поступает по сети и её нельзя целиком разместить в памяти. Главный вопрос — какой минимум информации о префиксе достаточен для будущего ответа.

Сумма и количество

Для суммы подходящих элементов достаточно двух переменных: накопленной суммы и, если нужен средний результат, количества принятых значений. Условие фильтра проверяется один раз на элемент. После прохода отдельно обрабатывают случай нулевого количества, чтобы не делить на ноль.

Максимум

Максимум непустой последовательности удобно инициализировать первым элементом, а не условным «очень маленьким» числом. После чтения префикса переменная равна его максимуму. Для максимума среди элементов по условию дополнительно хранят флаг, был ли найден хотя бы один кандидат.

Несколько характеристик

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

Почему память O(1)

Число переменных не растёт вместе с длиной потока. Однако размер самого большого числа иногда растёт по числу битов; в учебной оценке это обычно отделяют от количества хранимых элементов. Если позже требуется вывести все подходящие позиции, постоянной памяти уже недостаточно без повторного чтения.

Проектирование агрегата

Сформулируйте, что состояние означает после k элементов, затем выведите обновление при появлении k + 1-го. Проверьте пустой поток, один элемент, все отрицательные значения и отсутствие кандидатов. Этот приём строит алгоритм от инварианта, а не от набора случайных присваиваний.

Агрегат хранит только достаточную историю

Для максимальной суммы непрерывного фрагмента не нужен весь список кандидатов. После очередного значения current хранит лучшую сумму отрезка, который обязан закончиться здесь, а best — лучший ответ среди обработанных позиций. Если прежний хвост отрицателен, выгоднее начать заново.

def max_subarray_sum(values: list[int]) -> int:
    if not values:
        raise ValueError("empty sequence")
    current = best = values[0]
    for value in values[1:]:
        current = max(value, current + value)
        best = max(best, current)
    return best

assert max_subarray_sum([-2, 3, -1, 4, -5]) == 6

Алгоритм использует O(1) дополнительной памяти, если значения приходят потоком. Но восстановление границ оптимального отрезка потребует хранить несколько индексов — всё ещё не сам массив. Конкретный ответ определяет достаточное состояние.

Практика: поток температур

Из потока измерений за один проход найдите количество значений выше нуля, их среднее, максимальную длину подряд идущей положительной серии и позиции первого максимума. Нельзя сохранять измерения в коллекцию. До кода перечислите переменные состояния и смысл каждой после обработанного префикса. Проверьте пустой поток, все отрицательные значения, повтор максимума и серию, заканчивающуюся последним элементом.