Что: Семинар
Когда: Суббота, 16 сентября 2017, 16:20–18:00
Где: НГУ, ауд. 2128

Описание

Общие разговоры о курсе и домашках. О списывании.

Задача о наибольшей возрастающей подпоследовательности (LIP). Множество состояний/подзадач и рекуррентная формула. Восстановление решения = обратный ход. Лексикографически минимальная последовательность.

Задача поиска для каждого элемента массива ближайшего элемента слева, меньшего его. Решение со стеком за O(N).

Два указателя. Поиск самого длинного подотрезка с суммой не более M. Решение за O(N log N): бин. поиск и преф. суммы. Основное свойство: R*(L+1) >= R*(L). Алгоритм и анализ сложности O(N).