Назвемо неспадну підпослідовність , а незростаючу — , і оброблятимемо елементи зліва направо. Чи вдасться розподілити решту масиву, залежить лише від останнього елемента та останнього елемента . Новий елемент може приєднатися до , якщо він не менший за останній елемент , і до , якщо він не більший за останній елемент . Тож менший останній елемент і більший останній елемент ніколи не гірші. Порожня поводиться як , а порожня — як .
Досить двох чисел. Після обробки h_i один із двох останніх елементів — це саме h_i. Тому зберігаємо лише
: найбільший можливий останній елемент серед усіх допустимих розбиттів h_1, \ldots, h_i з h_i \in U (, якщо порожня, і «неможливо», якщо такого розбиття немає);
: найменший можливий останній елемент серед усіх допустимих розбиттів з h_i \in D (, якщо порожня, і «неможливо», якщо такого немає).
Спочатку u = +\infty, d = -\infty. Нехай p = h_i, x = h_{i+1}.
Із h_i \in U (останній елемент — , останній елемент — ): якщо p \le x, то може приєднатися до , це кандидат для нового ; якщо u \ge x, то може приєднатися до , це кандидат для нового .
Із h_i \in D (останній елемент — , останній елемент — ): якщо p \ge x, це кандидат для нового ; якщо d \le x, це кандидат для нового .
Новий — максимум його кандидатів, новий — мінімум його кандидатів («неможливо», якщо кандидатів немає). Відповідь YES тоді й лише тоді, коли наприкінці або можливе. Це часу, і масив навіть не треба зберігати.
Усі порівняння нестрогі, бо однакові значення дозволені в обох підпослідовностях: розв'язок для строго монотонних підпослідовностей не проходить. Тримайте «неможливо» окремо від «порожня» і від справжніх значень: 10^9 — допустиме значення, тож воно не може правити за .
Зауваження: як знайти розбиття. Для кожного запам'ятовуємо, який перехід дав і , і йдемо назад від i = n. Рівносильний жадібний алгоритм: якщо h_i підходить лише одній підпослідовності, віддаємо його їй; якщо обом, дивимося на наступне значення w \ne h_i і віддаємо h_i до , якщо w < h_i, і до інакше. Дивитися лише на h_{i+1} недостатньо, бо перед може стояти довга серія однакових значень.