Восстановление последовательности

[urdnot]

Этот вопрос по алгоритмам а не конкретно по С++, но раздел алгоритмы я не нашел поэтому написал сюда.

1. Есть конечная последовательность натуральных чисел обладающая следующим свойством:
(*) Любой суффикс этой последовательности лексикографически( только числа вместо букв) больше этой последовательности, например:
a = {3, 6, 10, 3, 6, 11, 3, 6, 99}, какой суффикс ни возьми: 99 >a, {6, 99} > a, {3, 6, 99} > a, ... и т.д
Потом мы берем и записываем все сдвиги этой последоваетльности т.е.
{6,10,3,6,11,3,6,99,3}; {10,3,6,11,3,6,99,3,6}; ... и т.д
Потом сортируем эти сдвиги лексикографически и берем последние элементы, получаем некую перестановку начальной последовательности. Для а ,например: {99, 10, 11, 3, 3, 3, 6, 6, 6} и вот надо воостановить по ней исходную последовательность.

2. Усложнение задачи 1. дана конечная последовательность натуральных чисел и мы слева направо начинаем искать максимальные подпоследовательности обладающие свойством (*) т.е. например:
a = {3,56,78, 5,6,4,2,5,7,8,9,2,4,1} -> {{3,56,78,5,6,4}, {2,5,7,8,9},{2,4},{1}}
Затем как в (1) для каждой подпоследовательности записываем все сдвиги (для посл. длин n , будет n всевозможных сдвигов)
Потом берем все последовательности и сортируем в лексикографичесокм порядке и берем их последние элементы
Получаем новую последовательность, по ней надо восстановить исходную.

Помогут любые дельные идеи, реализую уже я их сам.

[urdnot]

Первую задачу я придумал как решать, например:
a = {3,5,7,4,5,5} исходная последовательность (*)

Отсортированные сдвиги (**):
{3,5,7,4,5,5}
{4,5,5,3,5,7}
{5,3,5,7,4,5}
{5,5,3,5,7,4}
{5,7,4,5,5,3}
{7,4,5,5,3,5}

Последовательность по которой надо восстановить исходную {5,7,5,4,3,5}

1. {3,..., 5} -> {5, 3} (часть иходной последовательности)
{4,...., 7} -> {7,4}
{5,...., 5} - >{5, 5}
{5, ..., 4} -> { 4,5}
{5,..., 3} -> {3,5}
{7, ..., 5} -> {5,7}
Мы знаем что за 3 следует 5 (3 одна поэтому никаких проблем), за 4 следует 5 (тоже нет проблем), за 5 может идти 3,5,7 , но мы знаем что (**) отсортировано поэтому 3,5,7 сортируем и последовательновписываем после пятерок, с 7ой никактх проблемю Получаем:

2. {3, 5, ..., 5} - > {5,3,5}
{4, 5, ...., 7} -> {7,4,5}
{5, 3, ...., 5} - > {5,5,3}
{5, 5, ...., 4} -> {4,5,5}
{5, 7, ...., 3} -> {3,5,7}
{7, 4, ...., 5} -> {5,7,4}
Дальше проделываем тоже самое и получаем нужную последовательность с точность до поворота (этого достаточно)

Но вот в усложненном варианте (2ой задаче) такой подход не дает нужный результат.
Например исходная последовательность: {3,3,6,3,3} разобьется на {{3,3,6}, {3}, {3}} Затем после сдвигов и сортировок:
{3}
{3}
{3,3,6}
{3,6,3}
{6,3,3}
Получаем последовательность из последних элементов: {3,3,6,3,3}
Получаем пары:
{3, ... , 3} - {3, 3} ложная пара тройка зациклена на себе
{3, ..., 3} - {3, 3} снова ложная
{3, ..., 6} - {6,3}
{3, ..., 3} - {3,3}
{6, ...., 3} - {3, 6}

{3, 3, ..., 3} - неверно
{3, 3, ..., 3} - неверно
{3, 3, ..., 6}
{3, 6, ..., 3}
{6,3, ..., 3}