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