Ограниченная длинная возрастающая подпоследовательность

Question

Рассмотрим массив, который имеет N целые числа. Теперь нам дают индекс i, который может принимать значения от 1 через N, Этот конкретный индекс всегда должен присутствовать в LIS, который мы генерируем. Рассчитать LIS для каждого значения в i,

Как мы можем эффективно решить вышеуказанную проблему? Мое простое решение состоит в том, чтобы изменить индекс i для всех его значений и расчета LIS. Временная сложность возрастает до O (N² log (N)). Это может быть побито?

Пример:

N = 2. я = 1

Скажем, данный массив [1,2].

[1,2] или же [2, 2]

Самая длинная (строго) возрастающая подпоследовательность в каждом случае 2 а также 1,

Answer 1

Каноническая динамическая программа для LIS вычисляет, для каждого k, самая длинная возрастающая подпоследовательность элементов в индексе 1..k который включает в себя элемент в индексе k, Используя эти данные и данные зеркального отображения для максимально увеличивающихся подпоследовательностей k..nмы находим LIS, который включает в себя индекс k как союз самых старых k и самый длинный после k,

O(n log n)

Answer 2

Наличие индекса i, который должен быть в подпоследовательности, облегчает задачу просмотра влево и вправо и определения того, как далеко вы можете пойти, чтобы оставаться строго возрастающим. Это займет не более O(N) шагов.

Прямое решение теперь просто повторяет это для всех N значений в индексе i, что дает общее усилие O(N^2).

Но обратите внимание, что при изменении значения по индексу i вычисления, сделанные ранее, могут быть использованы повторно. Необходимо только проверить, может ли последовательность быть расширена за пределы i в любом направлении или нет. Если да, вы уже знаете, как далеко (или можете рассчитать его сейчас раз и навсегда).

Это сводит общее усилие к O(N).