Как самая длинная возрастающая подпоследовательность является особым случаем самого длинного пути в DAG?

Представьте себе проблему двумерной сетки. Вы находитесь на нижнем левом квадрате, и вам нужно добраться до верхнего правого квадрата. Можете ли вы представить себе ациклический DAG из этой схемы?

Теперь представьте, что некоторые квадраты запрещены. Запрещение квадратов может привести к «замку» (вы можете оказаться в ловушке), и теперь действительно важно выбрать какими путями следовать. С точки зрения графа, вы можете думать о запрете квадратов как об удалении вершин, и ваша цель — перейти от корня к одному конкретному узлу (приемнику).

Теперь вернемся к ЛИС. При решении LIS вам действительно нужно решить, какие числа вы выберете, а какие нет. Ограничение состоит в том, что всякий раз, когда вы выбираете одно число, вы не можете выбрать любое число, которое меньше, чем это число (вы выбираете числа по порядку).

Теперь мы можем смешать обе вещи. Представьте, что вы строите график из вашей последовательности чисел:

• Каждое число будет узлом.
• Number-node A has an edge to number-node B iff
  • B comes after A in the sequence
  • B больше, чем A по стоимости
• Есть специальный узел end
• У каждого узла есть край, ведущий к концу

Каждый путь на этом графе является действительной возрастающей подпоследовательностью. Проблема поиска ЛИС теперь представляет собой проблему поиска самого длинного пути на этом графе.

Если у нас есть массив чисел, например, 1, 5, 4, 8. Мы можем построить DAG следующим образом.

• Добавьте каждое число как вершину.
• Для каждой числовой вершины прибавьте исходящие ребра веса 1 ко всем большим числам после нее.
• Добавьте узел S, исходящие ребра которого имеют вес 0, ко всем числовым вершинам.
• Добавьте узел E, в который входят ребра веса 0 из всех вершин чисел.

Таким образом, задача «Самая длинная возрастающая подпоследовательность» превращается в задачу «Самый длинный путь от S к E».