Решение задачи #28. Python Яндекс CodeRun, НВП с восстановлением ответа

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: НВП с восстановлением ответа.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:
Дана последовательность, требуется найти её наибольшую возрастающую подпоследовательность.

Напомним:
Последовательность x называется подпоследовательностью последовательности y, если x получается из y удалением нескольких (возможно, нуля или всех) элементов.

Наибольшая возрастающая подпоследовательность - строго возрастающая подпоследовательность наибольшей длины.

Решение:

Python

import sys

def longest_increasing_subsequence(sequence):
    """
    Находит наибольшую возрастающую подпоследовательность.

    Args:
        sequence: Исходная последовательность.

    Returns:
        Наибольшая возрастающая подпоследовательность.
    """

    n = len(sequence)
    dp = [1] * n  # Длина наибольшей возрастающей подпоследовательности, заканчивающейся на i-м элементе
    parent = [-1] * n  # Родительский элемент для восстановления последовательности

    for i in range(1, n):
        for j in range(i):
            if sequence[j] < sequence[i] and dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
                parent[i] = j

    # Восстановление последовательности
    max_len = max(dp)
    index = dp.index(max_len)
    result = []
    while index != -1:
        result.append(sequence[index])
        index = parent[index]
    result.reverse()

    return result

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    sequence = list(map(int, sys.stdin.readline().split()))
    result = longest_increasing_subsequence(sequence)
    print(*result)
	

Объяснение кода

Инициализация:
dp: Список, где dp[i] хранит длину наибольшей возрастающей подпоследовательности, заканчивающейся на i-м элементе. Изначально все элементы равны 1, так как каждый элемент сам по себе является возрастающей подпоследовательностью длины 1.

parent: Список, где parent[i] хранит индекс элемента, предыдущего к i-му в наибольшей возрастающей подпоследовательности, заканчивающейся на i-м элементе. Это необходимо для последующего восстановления последовательности.

Основной цикл:
Внешний цикл перебирает все элементы последовательности. Внутренний цикл перебирает все предыдущие элементы.

Если текущий элемент больше предыдущего и мы можем получить более длинную возрастающую подпоследовательность, то обновляем dp[i] и parent[i].

Восстановление последовательности:
Находим индекс последнего элемента наибольшей возрастающей подпоследовательности. Используя массив parent, восстанавливаем всю последовательность, двигаясь от последнего элемента к первому.

Оптимизация:
Динамическое программирование: Позволяет эффективно решать задачу за время O(n^2).
Отсутствие лишних операций: Код оптимизирован для минимального количества операций.

Источник решения: hdhai.com