В данном решении нужен один дфс для каждой компоненты связности, а также посчитанные "влоб" факториал и степень двойки по модулю. Как же вы тогда себе представляете более простое решение?

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

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

Для случая разного роста решающим является следующее наблюдение. Рассмотрим, где в перестановке находится 1. Ясно, что она либо начало возрастающей подпоследовательности и тогда всё до нее должно убывать и быть началом убывающей подпоследовательности, либо она конец убывающей подпоследовательности и тогда всё после неё должно возрастать и быть концом возрастающей. Если выполнены оба эти условия, то построение очевидно: префикс до 1 — убывающий, суффикс, начиная с 1, — возрастающий. Иначе выполнен один из случаев и мы однозначно восстанавливаем какие-то куски наших подпоследовательностей и переходим либо к префиксу, либо к суффиксу перестановки.

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

Там, конечно, нужно аккуратно все закодить, но в итоге получается довольно простое линейное решение (дерево отрезков для минимума не нужно, для проверки на убывание и возрастание префиксов и суффиксов делается простая линейная ДП-шка).

Для возрастающей и убывающей последовательности можно придумать ДП. dp1[i] — минимальный конец возрастающей подпоследовательности в префиксе до i — го элемента при условии, что i — й элемент попал в убывающую, и dp2[i] — максимальный конец убывающей подпоследовательности в том же префиксе при условии, что i — й элемент попал в возрастающую. Пересчитывается за O(1).