Максимальная длина подряд идущих единиц после удаления одного элемента (Max Consecutive Ones After Deleting One Element)

Условие

Максимальная длина подряд идущих единиц после удаления одного элемента (Max Consecutive Ones After Deleting One Element)

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

Входные данные:

• nums – непустой массив целых чисел, каждый элемент равен 0 или 1

Выходные данные:

• Целое число – максимальная длина подряд идущих единиц после обязательного удаления одного элемента

Ограничения:

• 1 <= nums.length <= 10^5
• nums[i] равен 0 или 1

Пример:

Код на Go:

// Dostupno bez importa: sort, fmt, encoding/json
package main

func MaxOnes(nums []int) int {
    // TODO: napisthite reshenie zdes
    return 0
}

Код на Python:

# Доступно без импорта: json, sys, io
def max_ones(nums):
    # TODO: напишите решение здесь
    return 0

Ответ

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

Python:

def max_ones(nums):
    left = zeros = best = 0
    for right, value in enumerate(nums):
        zeros += value == 0
        while zeros > 1:
            zeros -= nums[left] == 0
            left += 1
        best = max(best, right - left)
    return best

Go:

func MaxOnes(nums []int) int {
    left, zeros, best := 0, 0, 0
    for right, value := range nums {
        if value == 0 { zeros++ }
        for zeros > 1 {
            if nums[left] == 0 { zeros-- }
            left++
        }
        if right-left > best { best = right-left }
    }
    return best
}

Каждый указатель проходит массив один раз: O(n) времени и O(1) памяти. Для [1,1,1] ответ 2, для [0] — 0; обязательное удаление учтено без особой ветки.