Семинар 1, Вводное занятие
Пятница, 10 сентября 2021
НГУ, ауд. 3122, НГУ, новый корпус
Общие разговоры о курсе и домашках. О списывании.
Задача о наибольшей возрастающей подпоследовательности (LIS). Множество состояний/подзадач и рекуррентная формула. Восстановление решения = обратный ход. Лексикографически минимальная последовательность.
Не успели: Задача поиска для каждого элемента массива ближайшего элемента слева, меньшего его. Решение со стеком за O(N).