Обход массивов и строк

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

Как получить два итога за один проход

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

Что дают повторные проходы по массиву

Можно сначала пройти массив ради суммы, затем второй раз ради количества положительных. Это всё ещё O(n), но дублирует обход и усложняет добавление новых агрегатов. Ещё хуже — для каждой позиции заново пересчитывать сумму префикса: тогда работа станет O(n²).

Почему повторное чтение не добавляет информации

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

Обновляем несколько агрегатов одним элементом

Один элемент независимо меняет несколько частей состояния: total увеличивается на его значение, а positive — на единицу только при value > 0. Оба обновления можно выполнить в одном проходе.

Что описывают total и positive

Перед обработкой позиции i:

• total равен сумме элементов на индексах [0, i);
• positive равен числу строго положительных элементов на тех же индексах.

После двух обновлений инвариант верен для префикса [0, i + 1).

Инициализация и два обновления на шаге

1. Инициализировать total = 0 и positive = 0: это правильное резюме пустого префикса.
2. Для каждого значения прибавить его к total.
3. Если значение строго больше нуля, увеличить positive.
4. После прохода вернуть оба агрегата.

Парный результат линейного прохода

C++17

#include <cassert>
#include <utility>
#include <vector>

using namespace std;

pair<long long, int> summarize(const vector<int>& values) {
    long long total = 0;
    int positive = 0;

    for (int value : values) {
        total += value;
        if (value > 0) {
            ++positive;
        }
    }

    return {total, positive};
}

int main() {
    assert((summarize({-1, 2, 3}) == pair<long long, int>(4, 2)));
    assert((summarize({0, -5}) == pair<long long, int>(-5, 0)));
    assert((summarize({}) == pair<long long, int>(0, 0)));
}

Python 3

def summarize(values: list[int]) -> tuple[int, int]:
    total = 0
    positive = 0

    for value in values:
        total += value
        if value > 0:
            positive += 1

    return total, positive


assert summarize([-1, 2, 3]) == (4, 2)
assert summarize([0, -5]) == (-5, 0)
assert summarize([]) == (0, 0)

Один проход и границы числового типа

Каждый из n элементов читается один раз: O(n) времени и O(1) дополнительной памяти. В C++ сумма хранится в long long, но даже он может переполниться, если контракт допускает слишком большие значения или слишком длинный массив. Целые Python расширяются автоматически.

Нули, пустой вход и большие суммы

• Пустой массив имеет сумму 0 и ноль положительных элементов.
• Ноль не считается положительным.
• Все числа отрицательные: счётчик остаётся нулём, сумма отрицательна.
• Большие по модулю числа требуют подходящего типа суммы в C++.
• Один элемент проверяет правильность инициализации и единственного обновления.

Проверяем нейтральные и смешанные входы

Используй [] → (0, 0), [5] → (5, 1), [0, -5] → (-5, 0), [-1, 2, 3] → (4, 2). Добавь значения около границ типа, если они разрешены условием.

Когда ответ является коротким резюме

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

Когда одного резюме массива мало

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

Меняют ли два прохода класс сложности

Вопрос. Два отдельных линейных прохода имеют O(n) или O(2n)?

Ответ. Асимптотически O(n), потому что постоянный множитель 2 отбрасывается. Один проход всё равно может быть проще для общего инварианта и уменьшает повторное чтение данных, но это не смена класса сложности.

Почему ноль требует отдельного теста

Вопрос. Почему нельзя написать positive += value >= 0?

Ответ. Контракт требует строго положительные элементы. Выражение >= 0 ошибочно посчитает нули; тест [0] сразу обнаружит эту границу.

Добавляем максимум к состоянию прохода

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

Самостоятельная задача о показаниях датчика

Задача 1

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

Точное состояние избавляет от повторных проходов

Хороший линейный проход начинается с точного состояния префикса: если каждый новый элемент обновляет его за O(1), весь ответ получается за одно чтение массива.