Самая длинная возрастающая подпоследовательность с разрешением K разрешена

Question

Здравствуйте, я застрял с моей домашней работой: заданная последовательность целых чисел, найдите самую длинную подпоследовательность, элементы которой упорядочены в возрастающем порядке.До k исключений, что означает самое большее k раз, следующее число в последовательности меньше предыдущего.Вывод должен быть длиной самой длинной такой подпоследовательности.

Я нашел много примеров нахождения LIS, даже один с одним разрешенным изменением, но я не знаю, как проверить с k изменениями.Вот ссылка на пост с одним изменением: https://www.geeksforgeeks.org/longest-increasing-subarray-with-one-change-allowed/amp/

Answer 1

Вы можете установить k счетчиков и пройти последовательность. Как только вы достигнете исключения, вы переходите к следующему счетчику. Если вы достигли k + 1-го счетчика, вы сбрасываете первый и сдвигаете все свои счетчики на единицу, так что n + 1-й счетчик становится n-м. С каждым шагом вы сохраняете текущий индекс вместе с суммой ваших k счетчиков в качестве общей длины последовательности. Возьмите максимум этого в конце

Пояснение: Вопрос только в том, где начинается самая длинная подпоследовательность. Если вы знаете, что знаете, как долго (до k + 1) исключение или конец последовательности). Пусть эта точка будет s. Самая длинная подпоследовательность может начинаться только с исключения или с начала последовательности. Если нет, вы можете добавить элемент s-1 в последовательность без добавления исключения и сформировать более длинную подпоследовательность. Приведенный выше метод вычисляет все возможные самые длинные подпоследовательности и в конце выбирает самого длинного кандидата.