Задача #2169
Работа со строками
(П. Говоров) Программист Павел "Setzor" любит составлять различные строки из букв. В файле содержится строка длиной не более 107 из заглавных букв латинского алфавита (ABC…Z).
Определите в прилагаемом файле максимальную длину подпоследовательности, которая состоит из двух последовательных частей (сначала 1 часть, затем 2):
в первой части символы расположены в алфавитном порядке, во второй в обратном алфавитном порядке. (1-ая и 2-ая часть могут быть различной длины).
Например, для строки QTUHHMSMJFSMECQ ответом будет являться подпоследовательность HHMSMJF (ответ 7), в которой 1 часть - HHMS, 2 - часть MJF (разделить можно также на части HHM и SMJF).
Войдите, чтобы история ответов и статистика сохранялись.
Решение
Ответ
17
1) Создадим 2 динамических массива для подсчета непрерывной
последовательности в алфавитном порядке, начиная с начала и конца.
2) Проверим каждые 2 соседних индекса двух массивов
и найдем макс. сумму.
Код:
f=open('24.txt')
s=f.readline()
dp1 = [0] * len(s)
dp2 = [0] * len(s)
dp1[0]=1
for i in range(1,len(s)):
if s[i] >= s[i-1]:
dp1[i] = dp1[i-1] + 1
else:
dp1[i] = 1
dp2[-1]=1
for i in range(len(s)-2,-1,-1):
if s[i] >= s[i+1]:
dp2[i] = dp2[i+1] + 1
else:
dp2[i] = 1
mx = 0
for i in range(1,len(s)):
mx = max(mx, dp1[i-1]+dp2[i])
print(mx)