Дана строка длины n, состоящая из 0 и 1. Необходимо найти длину её наибольшей подстроки, состоящей только из 1. Например, для строки 101101001001111011 ответом является число 4.

Для решения данной задачи написана такая программа:

S = input()
n = len(S)
ans = 0
for i in range(n):
t = 0
while i + t < n and S[i + t] == '1':
t += 1
ans = max(ans, t)
print(ans)
Определите асимптотику данного алгоритма.

Для понимания алгоритма и его асимптотики давайте поэтапно разберем его работу.

1. Программа начинается с чтения входной строки, которую мы обозначим как S.
2. Затем программа определяет длину строки n с помощью функции len(S). Обозначим это значение как n.
3. Далее создается переменная ans, которая инициализируется значением 0. Переменная ans будет содержать максимальную длину подстроки из единиц.
4. Запускается цикл по значениям от 0 до n-1, выполняя итерацию для каждого индекса строки.
5. Внутри цикла создается переменная t и ее значение устанавливается равным 0. Переменная t будет содержать текущую длину подстроки из единиц, начиная с текущего индекса.
6. Запускается внутренний цикл while, который будет выполняться до тех пор, пока сумма текущего индекса (i) и переменной t меньше n и символ строки S[i + t] равен '1'.
7. Внутри внутреннего цикла while переменная t увеличивается на 1 при каждой итерации.
8. После завершения внутреннего цикла while программа сравнивает текущее значение переменной ans с переменной t, и присваивает переменной ans максимальное из этих значений с помощью функции max(ans, t).
9. Цикл продолжается, пока не будут пройдены все элементы строки S.
10. После завершения цикла, программа выводит значение переменной ans, которая содержит максимальную длину подстроки из единиц.

Теперь рассмотрим асимптотику данного алгоритма. Асимптотика описывает скорость роста времени или памяти выполнения алгоритма по мере увеличения размера входных данных.

В данном случае, имеется один внешний цикл и один внутренний цикл while. Внешний цикл выполняется n раз, где n - длина входной строки S. Внутренний цикл while выполняется в худшем случае n раз для каждой итерации внешнего цикла, где каждую итерацию внутреннего цикла t увеличивается на 1.

Таким образом, общее количество итераций внутреннего цикла while зависит от количества подстрок из единиц в строке S.

Асимптотическая сложность данного алгоритма можно определить как O(n), где n - длина входной строки S.

Это связано с тем, что каждая итерация внешнего цикла выполняется за постоянное время O(1), а количество итераций внутреннего цикла while для каждой итерации внешнего цикла также линейно зависит от размера входных данных.

Итак, асимптотическая сложность алгоритма составляет O(n).