Не хочется изобретать велосипед - Общество дровосеков Бердичева по изучению Мишны
Jun. 28th, 2016
07:15 pm - Не хочется изобретать велосипед
Есть программистская задачка, на которую я не знаю правильного ответа.
Дан массив чисел. Нужно наиболее эффективным образом найти в нем такой непрерывный подмассив, чтобы среднее значение элементов этого подмассива и среднее значение остальных элементов максимально различались.
Например, пусть дан массив [99, 99, 99, 0, 0, 0, 100, 0, 0, 0].
Если мы возьмем подмассив, состоящий только из элемента 100, то среднее остальных элементов будет 3*99/9 = 33, а разность средних - 100-33 = 67.
Если брать в качестве подмассива группу из трех нулей, то среднее остальных равно (3*99+100)/7 = 56.714..., что хуже.
Если мы возьмем подмассив, состоящий из трех элементов, равных 99, то его среднее будет 99, среднее остальных элементов - 100/7 = 14.285..., а разность - 99-14.285... = 84.714... (максимум).
Но при увеличении количества нулей результат меняется. Пусть массив таков:
[99, 99, 99, (триста нулей), 100, (триста нулей)].
Тогда если взять подмассив [99, 99, 99], получим разность средних 99-100/601 = 98.8..., а если взять подмассив [100], получим 100-3*99/603=99.5..., и в этом случае подмассив [100] оптимален.
Но вот даже вышеупомянутую maximum subarray problem сформулировали в 1977 году, а линейное решение придумали далеко не мгновенно, так что я не оставляю надежды.
Потому что иначе ответ прост:
За один проход находим среднее массива, а так же самое большое и самое маленькое число в нем (и их позиции). Смотрим, что дальше от среднего в массиве - самое большое или самое маленькое число, и соответственно выбираем его как подмассив из 1 элемента.
Чуть более интеллектуальная разновидность: запоминаем не просто самое большое и самое маленькое число, а последовательности из них, и предпочитаем самую длинную последовательность. Вуаля, линейное решение.
Вот если размер подмассива фиксирован - то сложнее.
На первом проходе определяем среднее массива.
На втором проходе ищем подмассивы и запоминаем лучший найденный. Начинаем с первого числа и смотрим, больше оно или меньше среднего. Продолжаем добавлять к подмассиву средние числа, пока они находятся с той же стороны от среднего (при переносе каждого числа в подмассив, соответственно корректируем среднее оставшихся в массиве чисел). Если находится число с другой стороны от среднего, то запоминаем эту позицию (в каждый момент может быть запомнено не более одной позиции) и продолжаем пытаться добавить еще чисел, пока не случится одно из (а) среднее подмассива сравнится со средним остального массива или (б) найдется некоторое фиксированное количество X чисел подряд, которые попадают на другую сторону. Если одно их этих условий случается, плюем и отскакиваем на запомненную позицию, где опять начинаем с одного числа в подмассиве.
Введение ограничения числа X ограничивает оптимальность, но и ограничивает время выполнения O(X*N), то есть при малом X выходит O(N).
Тогда, подозреваю, более адекватная постановка была бы с поиском не максимальной разницы средних, а минимальной суммы квадратов отличий чисел от соотв. средних.
Edited at 2016-06-30 12:44 am (UTC)
Edited at 2016-06-30 01:18 am (UTC)
Ну будет у нас,
и дальше?