Question

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

.

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

#include
#include
#include
using namespace std;
int main()
{
string S;
cin >> S;
int n = S.size();
int ans = 0;
for (int i = 0; i < n; ++i)
{
int t = 0;
while (i + t < n && S[i + t] == '1')
++t;
ans = max(ans, t);
}
cout << ans << endl;
return 0;
}



Определите асимптотику данного алгоритма.

O(1)

O(logn)

O(√n)

O(n)

O(n^2)

Правильного ответа нет

Answer 1

Ответ: O(n^2)

Два независимых цикла, один из которых вложенный, дадут именно квадратичную асимптотику