Снова задачка

0

3

Теперь Седжвик.

Дано:

Напишите эффективную программу, которая определяет длину самой большой последовательности пробелов в данной строке, просматривая как можно меньшее количество символов.

Подсказка:

С возрастанием длины последовательности пробелов программа должна выполнятся быстрее.

Сам код подсчета пробелов может быть например таким:

#include <iostream>
#include <string>

int count( const std::string& input )
{
	int iSpaces = 0;

	for (int i = 0; i < input.size(); ++i)
		if (input[i] == ' ') ++iSpaces;

	return iSpaces;
}

int main()
{
	std::string input;
	
	std::cout << "Enter text: ";
	std::getline( std::cin, input );

	int numSpaces = count( input );

	std::cout << "Number of spaces: " << numSpaces << std::endl;
	std::cin.ignore();

	return 0;
}

То есть, интуиция мне подсказывает, что время выполнения искомой программы не менее чем O(N). Ну сосчитаем мы пробелы, дальше что? Загнать их в структуру данных X и отсортировать? Бред, по-моему...