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

Question

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

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

Пример:

N = 2. i = 1

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

[1,2] или [2, 2]

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

Answer 1

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

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

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

Это приноситсуммарное усилие до O (N).

Answer 2

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

O (n log n)