Максимальное количество последовательных 1 в строке

Question

Дана строка длиной N (может быть до 10 ^ 5), которая состоит только из 0 и 1. Мы должны удалить две подстроки длины K точно из исходной строки, чтобы максимизировать количество последовательных 1.

Например, предположим, что строка является 1100110001, а K = 1.

Таким образом, мы можем удалить две подстроки длины 1. Наилучший вариант здесь - удалить 0 на 3-м и 4-м местах и ​​получить вывод как 4 (новой строкой будет 11110001)

Если я попробую перебор, это наверняка истечет. Я не знаю, будет ли скользящее окно работать или нет. Может ли кто-нибудь дать мне подсказку о том, как поступить? Я не требую полного ответа, очевидно, мне помогут только некоторые подсказки. Заранее спасибо:)

Answer 1

Это довольно простое решение для динамического программирования.

Для каждого индекса i , рассчитать:

1. Длина последовательности 1 с, которая непосредственно предшествует ей, если ничего не было удалено;
2. Самая длинная последовательность из 1, которая может непосредственно предшествовать ей, если перед ней будет удалена ровно одна подстрока; и
3. Самая длинная последовательность из 1, которая может непосредственно предшествовать ей, если перед ней будет удалено ровно две подстроки.

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

Например, пусть BEST (i, r) будет лучшей длиной, непосредственно предшествующей позиции i после удаления r подстрок. Если i> = K , то вы можете удалить подстроку, заканчивающуюся на i и имеющую BEST (i, r) = BEST (iK, r-1) для r> 0 . Если string [i-1] = '1' , вы можете расширить последовательность с предыдущей позиции и получить BEST (i, r) = BEST (i-1, r) + 1 . Выберите наилучшую возможность для каждого i, r .

Самое большое значение, которое вы найдете на шаге (3) - это ответ.