Решение первой и второй подзадачи

Эти подзадачи являются упрощением задачи о наибольшей общей убывающей подпоследовательности и решаются стандартными алгоритмами за O(n^2m) и за O(nm) соответственно.

Решение третьей позадачи

Заметим, что любая неубывающая последовательность из нулей и единиц имеет следующий вид: сначала сколько-то нулей (возможно, ни одного), а потом сколько-то единиц (возможно, ни одной). Пусть a состоит из a₀ нулей и a₁ единиц, а b — из b₀ нулей и b₁ единиц. Тогда очевидно, что ответ равен min(a₀, b₀) + min(a₁, b₁). Решение работает за один линейный проход по последовательностям, асимптотика времени работы составляет O(n + m)

Полное решение

Воспользуемся наблюдением из прошлой подзадачи. Переберем количество нулей в ответе, обозначим его за k и найдем максимальное число единиц, которое может следовать за таким количеством нулей в какой-то общей подпоследовательности a и b. Заметим, что максимальное число единиц, которое может следовать за k нулями в какой-то подпоследовательности, для каждой из последовательностей равняется числу единиц после позиции, на которой в ней встречается k-й ноль. Для того, чтобы быстро определять, сколько единиц идет после k-го нуля, запомним для каждой из последовательностей позиции всех нулей. Также, для всех суффиксов каждой из последовательностей посчитаем, сколько единиц содержит этот суффикс. Весь предподсчет может быть выполнен за линейное время. Теперь, когда мы умеем быстро определять для каждого k максимальное количество единиц, которое может следовать за k нулями в общей подпоследовательности, переберем количество нулей, и для каждого из них посчитаем максимальный ответ. Из всех получившихся ответов возьмем максимальный, он и будет являться ответом на задачу. Асимптотика времени работы этого решения составляет O(n + m).