Подход алгоритма онлайн для чередующейся подпоследовательности

Question

Рассмотрим последовательность A = a1, a2, a3, ... an целых чисел. Подпоследовательность B в A - это последовательность B = b1, b2, ....,bn, которая создается из A путем удаления некоторых элементов, но с соблюдением порядка. Для целочисленной последовательности A цель состоит в том, чтобы вычислить чередующуюся подпоследовательность B, то есть последовательность b1, ... bn, такую, что для всех i в {2, 3, ..., m-1}, если b{i-1} b{i+1}, а если b{i-1} > b{i}, то b{i}

---

Рассмотрим онлайновую версию проблемы, где последовательность A задается поэлементно, и каждый раз необходимо непосредственно решить, следует ли включать следующий элемент в подпоследовательность B. Можно ли достичь постоянного конкурентного соотношения (с помощью детерминированного онлайн-алгоритма)? Либо дайте онлайн алгоритм, который достигает постоянного конкурентного соотношения, либо покажите, что невозможно найти такой онлайн алгоритм.

Предположим последовательность [9,8,9,8,9,8, ...., 9,8,9,8,2,1,2,9,8,9, ..., 8,9,8,9,8,9]

Моя аргументация: алгоритм должен немедленно решить, вставлять ли входящий номер в подпоследовательность. Если алгоритм теперь получает числа 1, затем 2, то 2, он в конечном итоге решит, что они являются частью последовательности и, таким образом, по нелинейному коэффициенту хуже, чем оптимальное решение n-3.

-> Нет постоянного конкурентного соотношения!

Это правильная аргументация?

Answer 1

Если я понял, что вы имели в виду, ваш аргумент верен, но последовательность, которую вы привели в примере, неверна. Например, алгоритм может выбрать все 9 и 8.
Вы можете немного изменить свой аргумент, чтобы сделать его более точным, например, рассмотреть последовательность

3,4,3,4,3,4,......, 1/5,2/6,1/5,2/6,....

Объяснение:
Вы начинаете последовательность с 3,4,3,4,... и т.д., пока алгоритм не выберет два числа. Если это никогда не происходит, это, очевидно, не является конкурентным 0/1 снаружи n)
Если алгоритм выбрал 3, тогда 4алгоритм должен затем принять число ниже, чем 4, Продолжая с 5,6,5,6,... алгоритм не может принимать другое число.
Если алгоритм решил взять 4 затем 3По аналогичному резонансу мы можем легко увидеть, как продолжить 1,2,1,2,... препятствует тому, чтобы алгоритм взял другой nubmer.
Таким образом, в любом случае алгоритм не может занять больше 2 номера для каждого nчто, как вы заявили, не является постоянным конкурентным соотношением.