Наибольшая длина непрерывного отрезка из единиц после удаления одного элемента

Условие

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

assert(maxOnes(new int[]{1, 1, 0, 1})) == 3
assert(maxOnes(new int[]{1, 1, 0, 0, 1})) == 2

Ответ

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

public int maxOnes(int[] values) {
    int left = 0, zeros = 0, best = 0;
    for (int right = 0; right < values.length; right++) {
        if (values[right] == 0) zeros++;
        while (zeros > 1) {
            if (values[left++] == 0) zeros--;
        }
        best = Math.max(best, right - left);
    }
    return best;
}

Время O(n), память O(1). Для массива из одних единиц ответ n−1, не n. Для одного элемента ответ 0; пустой массив здесь также возвращает 0 по выбранному соглашению, хотя удалить из него элемент нельзя.