Переверните последовательные нули в единицы за k операций, чтобы получить максимальное количество единиц, найдите максимальное количество единиц

Подход с использованием скользящего окна будет работать. Чтобы максимизировать количество последовательных единиц, имеет смысл выбирать только соседние группы нулей для преобразования в единицы (т.е. без каких-либо невыбранных нулей между ними), в противном случае мы тратим наши k на создание непересекающихся островов единиц, что отходы. Таким образом, вы сначала выбираете первые k группы нулей, затем отменяете выбор первой из них и добавляете следующую и т. д., «скользя» по вводу, каждый раз проверяя, какой из этих вариантов представляет самый длинный результат. .

Вот реализация подхода скользящего окна, написанная на JavaScript:

function solve(pattern, k) {
    let start = 0; // start index of the "window"
    let size = 0; // Longest result found so far
    for (let end = 0; end < pattern.length; end++) { // Grow window to the right
        if (pattern[end] == "0" && (end == 0 || pattern[end-1] == "1")) {
            // We encounter a first 0 in a group of 0s
            k--; // Adjust the number of 0-groups we are still allowed to consume
            if (k < 0) { // Must give up a group of 0s
                // Shrink window from the left side, dropping one 0-group
                while (pattern[start] == 1) start++;
                while (pattern[start] == 0) start++;
                k++; // ...and allow for one more 0-group at the right
            }
        }
        if (end - start >= size) size = end + 1 - start; // best so far
    }
    return size;
}

let count = solve("1100101001", 2);
console.info(count);

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

По очевидным причинам начало этой последовательности — это либо начало ввода, либо 1, которому предшествует 0, а конец — это либо конец ввода, либо 1, за которой следует 0.

Перепишите входные данные в кодировку длины. Итак, 11000100001 Превращается в «0,2,3,1,4,1» (для: 0 нулей, затем 2 единицы, затем 3 нуля, 1 единица, 4 нуля, 1 единица). Для этого алгоритма мы всегда должны начинать с подсчета нулей, следовательно, мы начинаем с «нулевых нулей».

Вам нужна наибольшая доступная сумма из 4 последовательных чисел, если начало четное, и 5 последовательных чисел, если начальный индекс нечетный.

Это можно легко сделать с помощью скользящих окон: сложите первые 4 числа и сохраните это значение.

Затем удалите первое число и добавьте 2 последующих числа. Если это больше, чем то, что вы сохранили раньше, сохраните это.

Затем удалите 2 числа спереди и добавьте 1 сзади.

Затем удалите 1 число спереди и добавьте 2 сзади.

Продолжайте, пока не дойдете до конца. Вернуть наибольшее «сохраненное» число.