Должна ли подпоследовательность быть непрерывной

Question

Я новичок в динамическом программировании и читал о проблеме Longest Increasing Subsequence(LIS).

В решении указано, что последовательность не должна быть непрерывной, как в исходном массиве. Элементы могут быть пропущены между ними; но я был под другим впечатлением.

Не могли бы вы помочь прояснить эту путаницу.

Скажем, например: a = {10,22,9,33,55,66,12,90}ЛИС {10,22,33,55,66,90} => 6

Тем не менее, я думал, что это будет {33,55,66}

Спасибо

Answer 1

Подпоследовательность не должна быть непрерывной. Подпоследовательность формируется путем удаления нуля или более элементов из массива. Субарай, с другой стороны, всегда непрерывен. Давайте возьмем ваш пример:

a = {10,22,9,33,55,66,12,90}

Вот,{10,22,33,55,66,90} самая длинная возрастающая подпоследовательность и {33,55,66} это самый длинный увеличивающийся подмассив.

Итак, то, что вы в основном отвечаете, - это решение самой большой проблемы с подмассивом.