Решил. Примера кода перед собой нет, но смысл в следующем. Создаем дерево со следующей структурой узлов.
int _index; // Индекс элемента массива
int _level; // Уровень узла в дереве
NodeType _parent; // Родительский узел
конструктор принимает массив элементов, индекс элемента в узле, и уровень текущего узла + 1
Корневой элемент имеет индекс -1. Далее мы создаем потомков из ВСЕХ элементов. Для каждого следующего элемента потомками будут те, которые (по индексу) идут после текущего и оба значения которых больше значений текущего. То есть у элемента 7 2 потомков уже не будет, потому что все первые элементы не больше семерки.
Если потомков нет, то отмечаем узле как лист (добавляем его куда нибудь в массив листов дерева). Далее от листа перемещаемся вверх (по полю _parent
) и получаем результирующий массив. Так как в листе у нас есть поле _level
, то мы сразу будем знать количество элементов в массиве. Самая длинная цепочка будет ответом.
Так же можно оптимизировать алгоритм и отбросить лишние варианты еще на этапе построения дерева. Например, можно добавлять в кэш максимальную длину цепочки (на том этапе, когда мы выясняем, что узел является листомм). И если мы выяснили, что после элемента (конечно же мы проверяем его по индексу, а не по значению) "2 6" у нас следует 2 элемента, то дойдя до того места, где у нас встречается этот элемент, мы сравниваем его уровень + кэшированное количество элементов после него с наибольшей на данный момент цепочкой, и если кэшированное значение больше, то отбрасываем этот вариант сразу. Есть возможность и еще сократить время действия алгоритма, но я их приводить уже не буду.