Решение задачи НВП с восстановлением ответа с Яндекс Контест

Без пояснения   Просмотров: 2307

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


Код 

n = int(input())
a = list(map(int, input().split()))
dp = [1] * n
for i in range(1, len(a)):
    for j in range(i - 1, -1, -1):
        if a[i] > a[j]:
            dp[i] = max(dp[i], dp[j] + 1)
mx = max(dp)
res = []
i = n - 1
while mx > 0:
    if dp[i] == mx:
        res.append(a[i])
        mx -= 1
    i -= 1
print(*res[::-1])

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp