минимизировать отклонение k целых чисел от n упорядоченных целых чисел

Question

Учитывая серию из n целых чисел и числа k, n> k, каково решение минимизации дисперсии k новых целых чисел? Вы можете добавить любые последовательные целые числа в новое целое число и, таким образом, уменьшить n целых чисел до k целых чисел.

Вот пример. При n = 4, k = 2, ряд целых чисел равен 4,4,1,1. Решение составляет 4,6 вместо 8,2 или 9,1.

Я придумал жадный алгоритм, который выглядит следующим образом: для всех возможных новых целых чисел минимизируйте абсолютное значение разности этого целого и среднее значение всех целых чисел. Но в некоторых случаях это не сработает. Существует ли эффективный алгоритм?

Answer 1

Дисперсия случайной величины X равна E [(X - E [X])^2]. Здесь X - случайный элемент выходного списка. Мы знаем, что E [X] равно сумме входных чисел, деленных на k, поэтому эта цель эквивалентна сумме (x - sum/k)^2 по выходным значениям x. Это можно сделать, слегка изменив алгоритм переноса слов: Word wrap to X lines instead of maximum width (Least raggedness)