Максимальная последовательность единиц

Постановка задачи

nums = [1, 1, 0, 1, 1, 1]

3

nums = [1, 0, 1, 1, 0, 1]

2

Решение

Задача на нахождение количества последовательных единиц - это классика на простой перебор элементов массива за один проход.

Идея решения:

Можно заметить, что для определения количества единиц в какой-либо последовательности 1 (серии) в массиве нам в целом не нужно знать как расположены нули или как расположены другие последовательности единиц.

Представьте, что мы смотрим на текущий элемент в массиве c индексом i. Тут возможны два случая: текущий элемент 1 или 0. Если мы видим 1, то это либо начало новой серии, либо продолжение текущей серии (которая началась где-то раньше индекса i). Если же мы видим 0, то это означает завершение текущей серии, если она была.

Таким образом все, что нам нужно - это счетчик единиц, которые мы уже видели в серии и проверка текущего элемента массива (чтобы увеличить или сбросить серию). Нам достаточно перебирать элементы массива и подсчитывать текущую серию. Если текущий элемент массива это 1 - мы увеличиваем счетчик, а eсли мы встречаем 0 - это означает завершение текущей серии и в этот момент мы можем запоминать длину максимальной серии.

Нам потребуется два счетчика: один для текущей серии единиц count, другой - для хранения найденного максимума maxCount, который мы встречали до сих пор. Нам нужно пройти по массиву ровно один раз, обновляя эти счетчики.

Основные шаги:

1. Заводим переменные count (текущая серия) и maxCount (максимальная серия), обе 0.
2. Идем циклом по массиву:
   • Если текущий элемент - 1, увеличиваем count на 1.
   • Если текущий элемент - 0, сравниваем count с maxCount, обновляем максимум, если нужно, и обнуляем count.
3. После цикла делаем финальное сравнение count и maxCount (на случай, если массив закончился единицей).
4. Возвращаем maxCount.

Пример 1:

В самом начале count = 0, maxCount = 0.

На первой итерации цикла nums[i] равно 1, мы увеличиваем count:

На второй итерации цикла nums[i] также равно 1, опять увеличиваем count:

На третьей итерации nums[i] равно 0, это означает, что текущая серия закончилась, нужно сбросить count и обновить maxCount:

На четвертой итерации nums[i] равно 1, начало новой серии, мы увеличиваем count:

Пятая и шестая итерации проверяют, что nums[i] равно 1 и увеличивают count:

Наконец после выхода из цикла делаем финальную проверку и обновляем maxCount:

Таким образом результат (maxCount) для этого примера будет равен 3 - это верный результат.

Оценка сложности

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

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

В нашем решении мы проходим по массиву ровно один раз с помощью одного цикла. Каждая итерация цикла выполняет операции с константным временем: сравнение числа с нулем, инкремент счетчика и вызов функции max (которая выполняет O(1) операций).

Таким образом общее количество операций прямо пропорционально количеству элементов в массиве (n). Если в массиве 10 элементов, будет 10 итераций. Если миллион - миллион итераций. Это линейная сложность: O(n).

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

Мы используем фиксированное количество дополнительной памяти, которое не зависит от размера входного массива.

Для решения нам требуется только несколько переменных типа int (count, maxCount и счетчик цикла i). Даже если входной массив будет содержать миллиард элементов, нам всё равно понадобятся только эти переменные для хранения текущего и максимального результата.

Таким образом это константная сложность, так как мы не создаем копий массива, дополнительных хеш-таблиц или списков: O(1).

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

Код решения

После того как мы обсудили решение, проверили на тестовых примерах, оценили временную и пространсвенную сложность и выяснили, что наше решение является оптимальным, можем написать код решения.

func findMaxConsecutiveOnes(nums []int) int {
    count := 0
    maxCount := 0
    
    for i := 0; i < len(nums); i++ {
        if nums[i] == 1 {
            count++
        } else {
            // Встретили ноль: обновляем максимум и сбрасываем счетчик
            maxCount = max(maxCount, count)
            count = 0
        }
    }
    
    // Финальная проверка после выхода из цикла
    return max(maxCount, count)
}

Итоги

1. Паттерн "cчетчик и максимум": это классический прием для задач на перебор в массиве и подсчете. Мы используем одну переменную для накопления текущего результата и вторую для глобального максимума.
2. Важность "пост-условия": распространенная ошибка - забыть финальную проверку после завершения цикла. Если массив заканчивается единицами (например, [0, 1, 1]), блок else не сработает, и финальный результат останется в count.
3. Линейная сложность: для массивов проход в один цикл O(n) при использовании константной памяти O(1) является эталонным решением. Если вы видите, что задачу можно решить без вложенных циклов, всегда стремитесь к этому.
4. Универсальность логики: как видно из примеров на разных языках, алгоритмическая суть не меняется от синтаксиса. Главное - это контроль текущей серии и корректный сброс при встрече "разделителя" - элемента сбрасываюшего серию (в данном случае - нуля).