Поиск элементов [pascal]

[BDA]

Сообщение от s-andriano

Кстати, до прохода по массиву мы не знаем "нужно длины", так что сначала придется помещать в список все последовательности (как смещение, так и длину) с длиной не меньше уже обнаруженной, а потом дополнительно просматривать список для нахождения последовательностей нужной длины.

Сначала допсписок начал пуст, а максимальная длина равна 0. Затем берем элемент из списка и идем по списку, пока не встретим отличный, считая длину подпоследовательности. Если длина больше максимальной, то очищаем допсписок и заносим начало подпоследовательности. Если равна, то только заносим. Таким образом, после 1 прохода по массиву имеем максимальную длину и список начал подпоследовательностей. Возможно, имеет смысл хранить не только начала подпоследовательностей, но и концы.

Сообщение от illuminato

BDA, спасибо большое. Вы мне очень помогли и сохранили моё время.

Пожалуйста. Не забудьте протестировать на всякие случаи.

[BDA]

<double-post>

[s-andriano]

Сообщение от BDA

...Если длина больше максимальной, то очищаем допсписок...

А какова сложность очистки списка?
Если больше, чем O(1), не приведет ли это к росту сложности алгоритма выше O(N)?

Возможно, имеет смысл хранить не только начала подпоследовательностей, но и концы.

Я предложил хранить длину. Мне кажется, это удобнее.

[BDA]

Сообщение от s-andriano

А какова сложность очистки списка?
Если больше, чем O(1), не приведет ли это к росту сложности алгоритма выше O(N)?

Скорее всего выше. Можно попробовать соптимизировать
Запихивать в стек вместо списка и без очистки, при этом считая k количество подпоследовательностей максимальной длины. Таким образом, первые k сохраненных подпоследовательностей (на вершине стека) будут искомыми, а остальные можно просто удалить затем из стека. То есть почти то, что Вы написали в 19 посте, но без дополнительного просмотра списка.

[s-andriano]

Красивое решение.
Я сначала подумал, что, раз уж мы решились на выделение памяти объема O(N), то стек можно организовать посредством массива, а не посредством выделения памяти для каждого элемента. Удалений из середины наш список не предполагает, а очистка массива при оптимальной реализации занимает O(1).