Г-н Фаршеклоакин (spamsink) wrote,
Г-н Фаршеклоакин
spamsink

Не хочется изобретать велосипед

Есть программистская задачка, на которую я не знаю правильного ответа.

Дан массив чисел. Нужно наиболее эффективным образом найти в нем такой непрерывный подмассив, чтобы среднее значение элементов этого подмассива и среднее значение остальных элементов максимально различались.

Например, пусть дан массив [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] оптимален.
Tags: puzzle
Subscribe

  • Это что за орфографические новости?

    В одном ютубовском ролике, который автор стесняется озвучивать голосом, в субтитрах замечены слова вида puttx, poppx, havx, gettx, eatx, gox. Судя…

  • Юникод для новояза

    В списке кодов, предложенных к включению в юникод версии 14: 1AC9..1ACA 2 COMBINING DOUBLE PLUS SIGN ABOVE COMBINING DOUBLE PLUS SIGN BELOW Также…

  • Ни на что не намекаю, просто песенку пою

    Подсадил меня Ютуб в последние дни на песенный конкурс для детей, оставшихся без попечения родителей "Ты супер!" (по-моему, весьма полезное,…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 33 comments

  • Это что за орфографические новости?

    В одном ютубовском ролике, который автор стесняется озвучивать голосом, в субтитрах замечены слова вида puttx, poppx, havx, gettx, eatx, gox. Судя…

  • Юникод для новояза

    В списке кодов, предложенных к включению в юникод версии 14: 1AC9..1ACA 2 COMBINING DOUBLE PLUS SIGN ABOVE COMBINING DOUBLE PLUS SIGN BELOW Также…

  • Ни на что не намекаю, просто песенку пою

    Подсадил меня Ютуб в последние дни на песенный конкурс для детей, оставшихся без попечения родителей "Ты супер!" (по-моему, весьма полезное,…