Взрывопотам

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

Для решения задачи можно было заметить, что если приписать ко входному массиву в конец его копию, то после построения такого леса самый глубокий лист в нем будет ответом на задачу, с учетом всех возможных циклических сдвигов. Чтобы это доказать, можно заметить, что разность номеров листа и корня не больше n, кроме того, любой путь обязательно будет присутствовать в этом дереве. Таким образом, получили решение, работающее за O(n).