Это возможно . Но тогда вам каждый раз нужно возвращать четыре значения: самая длинная подпоследовательность, которая начинается в левом конце «среза» (это может быть ноль), самая длинная подпоследовательность «в середине», самая длинная подпоследовательность он заканчивается на правом конце «среза» (это также может быть ноль), и если строка является просто последовательностью не-Y символов (логическое значение). Фактически, четвертый элемент может быть получен путем проверки, равен ли один из элементов в первых трех элементам длине, но это, вероятно, легче реализовать.
Почему это важно? Потому что последовательность не y s может проходить «через» деление. Например:
abcde<b>Y</b>fghi jkl<b>Y</b>mnopqr
здесь, если мы разбиваем его по середине (или любым другим способом, который не является «постоянным» и «покоем»).
Так что здесь у нас есть несколько случаев:
- пустая строка возвращает
(0, 0, 0, True),
- непустая строка, отличная от
Y, мы возвращаем (1, 1, 1, True);
- для одиночной строки
Y мы возвращаем (0, 0, 0, False);
- рекурсивный случай, который делит строку на две части и затем применяет логику «слияния» к результатам.
«Логика слияния» довольно сложна, тем более что возможно, что оба «субликса» содержат только строки, не являющиеся Y. После нарезки мы получаем две тройки (a0, a1, a2, a3) и (b0, b1, b2, b3) и получаем три кортежа (c0, c1, c2, c3).
Если a3 = True и b3 = True, то, конечно, это означает, что текущий срез также не содержит Y. Таким образом, мы можем вывести это:
c3 = a3 and b3
, учитывая, что a3 имеет место, тогда он утверждает, что c0 = a0 + b0 с тех пор a0 не имеет Y, и, таким образом, левая "последовательность" равна всей длине подпоследовательности плюс левого подпоследовательность правой части. Если a3 не удерживает , c0 просто a0.
Учитывая, что выполняется b3, то оно содержит c2 = a2 + b2 по тем же рассуждениям, что и выше, если нет, то a2 = b2.
Теперь элемент в середине - это максимум три элемента:
- элемент посередине левого среза
a1;
- элемент в середине правого среза
b1; и
- сумма
a2 и b0, поскольку возможны совпадения, а затем это сумма двух.
Таким образом, мы возвращаем максимум дерева.
Так в Python это выглядит так:
def longestNoY(string, start, end):
if start == end:
return (0, 0, 0, True)
elif start+1 == end:
if string[start] == 'y':
return (0, 0, 0, False)
else:
return (1, 1, 1, True)
else:
mid = (start + end)//2
a0, a1, a2, a3 = longestNoY(string, start, mid)
b0, b1, b2, b3 = longestNoY(string, mid, end)
c3 = a3 and b3
c0 = a0 + a3 * b0
c2 = b2 + b3 * a2
c1 = max(a1, b1, a2 + b0)
return (c0, c1, c2, c3)
Окончательный результат - максимум первых трех элементов в кортеже.
Для данной строки образца мы получаем:
(1, 1, 1, True) a
(1, 1, 1, True) b
(2, 2, 2, True) ab
(0, 0, 0, False) y
(1, 1, 1, True) d
(0, 1, 1, False) yd
(2, 2, 1, False) abyd
(1, 1, 1, True) e
(1, 1, 1, True) f
(2, 2, 2, True) ef
(0, 0, 0, False) y
(1, 1, 1, True) h
(1, 1, 1, True) i
(2, 2, 2, True) hi
(0, 2, 2, False) yhi
(2, 2, 2, False) efyhi
(2, 3, 2, False) abydefyhi
(2, 3, 2, False)
но, как говорится, для меня это выглядит как ненужная сложная процедура для конструирования чего-либо, что с точки зрения сложности времени такое же, как обход, но обычно более дорого (вызовы функций, создание новых объектов и т. Д.). Тем более что линейный обход это просто:
def longestNoY(string):
mx = 0
cur = 0
for c in string:
if c == 'y':
mx = max(mx, cur)
cur = 0
else:
cur += 1
return mx
Однако здесь есть преимущество в том, что описанный выше алгоритм может использоваться для распараллеливания . Если, например, строка огромна, то можно использовать вышеприведенное, так что каждое ядро может считать это. Однако в этом случае, вероятно, выгодно использовать итеративный уровень на уровне «ядра» и использовать только вышеперечисленное для «распределения» работы и «сбора» результатов.