Разбор задачи про замену 0 и максимальную последовательность 1

Эту задачу можно эффективно решить за линейное время и константную память. Мне известно как минимум 3 таких решения. Но приведу, на мой взгляд, наиболее элегантное и понятное из них.

Идея решения состоит в том, чтобы обходить исходный список и сохранять индекс предыдущего 0, который мы встретили. Так мы можем легко узнать общее количество 1 между текущим и предыдущим 0 для каждого последующего 0.

Временная сложность приведенного на скриншоте выше решения составляет O(n) и не требует дополнительной памяти.