Разделяй и властвуй. Задачи на прямой

Для более полного понимания происходящего можно (но не обязательно!) пройти 5.2.Умножение чисел

• Подотрезок максимальной суммы
• Экстремальные точки на прямой (например, минимизируем сумму расстояний до остальных, сумму квадратов расстояний до остальных)
• Две ближайшие точки в 2D, в 3D за $O(n \log n)$