Проблема: задан массив A
, который представляет точки на линии, например. [5,-4,1,3,6]
и номер M=3
, найдите максимальное подмножество точек в пределах A
, расстояние между которыми несколько кратно M
.Найти подмножество точек, расстояние между которыми кратно числу
В этом примере двумя возможными подмножествами будут [-4,5]
(расстояние 9) и [3,6]
(расстояние 3).
Очевидным решением для перебора является вычисление расстояния между каждой парой точек в O(N^2)
времени, а затем построение набора кандидатов путем постепенного наращивания подмножеств.
Есть ли более эффективное решение?
Ах, так просто, спасибо! Хотя я до сих пор не совсем понимаю, почему отрицательные числа нужно обрабатывать по-разному. – curpickled
Это просто зависит от того, как работает модуль на любом используемом вами языке. Это скорее сложная деталь реализации, а не часть алгоритма, который я предполагаю. – samgak