Как понимать подпоследовательность?

Question

[Александр]

Например, есть последовательность пар. Это понятно. А что значит подпоследовательность? Как она реализуется в C++?

Answer 1

[OCTAGRAM]

Это любая последовательность, состоящая из подмножества элементов последовательности, сохраняющая их порядок.

Как придумаете, так и будет работать. Вектором или массивом логических значений можно задать, какие элементы последовательности выбираются для участия в подпоследовательности. Или множеством индексов элементов. Или возрастающим массивом/вектором индексов.

Comments

[Александр]

Можете пример какой то? Сложно понять.

[OCTAGRAM]

Последовательность:
│10 20 30 40 50│
Трафарет:
│ ██ ██│
Накладываем трафарет, получаем подпоследовательность:
│10 ██ 30 40 ██│
Или, схлопнув вычеркнутое:
│10 30 40│

Трафарет, задающий подпоследовательность, можно задать как множество. Множество можно задать массивом логических значений:
[true, false, true, true, false]
Или множеством индексов
[2, 0, 3]
Если это множество упорядочить, получится массив индексов
[0, 2, 3]
Первый элемент подпоследовательности имеет индекс 0, а в последовательности под этим индексом находится 10. Второй элемент подпоследовательности имеет индекс 2, и по этому индексу 30. Аналогично 40.

[Александр]

Хорошо. Это понятно. А как понять следующее ?

Дана последовательность пар.
В этой последовательности могут встречаться непрерывные подпоследовательности.

[Евгений Шатунов]

Александр, так и понять.

[OCTAGRAM]

Александр, В последовательности длины n можно разглядеть O(n²) непрерывных подпоследовательностей. Предложение выглядит так, будто обрывается на середине, а дальше должно было быть написано какое-нибудь интересное свойство этих подпоследовательностей.

Наиболее логичное предположение о том, что же это за свойство, — это то, что второй элемент пары равен первому элементу следующей за ним пары, и так по цепочке.

[Александр]

OCTAGRAM, Полный текст такой.
Дана последовательность пар (int Х : int Y). Пары упорядочены по значениям Х.

В этой последовательности могут встречаться непрерывные подпоследовательности, состоящие из идентичных отсчетов. Идентичные отсчеты имеют одинаковые значения Y.

[OCTAGRAM]

Александр, а, ну тогда всё ясно. Тогда проще всего задать непрерывную подпоследовательность краями, либо началом и длиной.

Могут встречаться — значит, они не заданы, а их можно, наоборот, найти. И, скорее всего, интерес представляют только подпоследовательности наибольшей длины.

Делается проход от начала до конца, и пока Y сохраняется, увеличивать длину, а как поменялся, так зарегистрировать подпоследовательность и сбросить длину. И после прохода по всей последовательности регистрируется подпоследовательность, которая была в конце.

А, может, то обстоятельство, что что-то встречается, дано просто для справки, то есть, используется косвенно.