Дана строка длины 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)
Правильного ответа нет
Answers & Comments
Ответ: O(n^2)
Два независимых цикла, один из которых вложенный, дадут именно квадратичную асимптотику