История изменений
Исправление Waterlaz, (текущая версия) :
и вообще я не понял длинной строки return…
Идея алгоритма(упрощенная):
Нужно найти сумму квадратов m максимальных чисел в массиве a, которую обозначим f(a, m).
Выбираем какой-то элемент массива a. Для простоты возьмем a[0].
Разделим массив a на две части x и y такие, что:
x[i] > a[0]
y[i] <= a[0]
Пусть length(x) и length(y) - длины массивов, тогда
Если length(x)>m, f(a, m) = f(x, m).
Если length(x)<=m, то f(a, m) = sumSquared(x) + f(y, m-length(x))
Исправление Waterlaz, :
и вообще я не понял длинной строки return…
Идея алгоритма(упрощенная):
Нужно найти сумму квадратов m максимальных чисел в массиве a, которую обозначим f(a, m).
Выбираем какой-то элемент массива a. Для простоты возьмем a[0].
Разделим массив a на две части x и y такие, что:
x > a[0]
y <= a[0]
Пусть length(x) и length(y) - длины массивов, тогда
Если length(x)>m, f(a, m) = f(x, m).
Если length(x)<=m, то f(a, m) = sumSquared(x) + f(y, m-length(x))
Исходная версия Waterlaz, :
и вообще я не понял длинной строки return…
Идея алгоритма(упрощенная):
Нужно найти сумму квадратов m максимальных чисел в массиве a, которую обозначим f(a, m).
Выбираем какой-то элемент массива a. Для простоты возьмем a[0].
Разделим массив a на две части x и y такие, что:
x > a[0]
y <= a[0]
пусть length(x) и length(y) - длины массивов, тогда
Если length(x)>m, f(a, m) = f(x, m).
Если length(x)<=m, то f(a, m) = sumSquared(x) + f(y, m-length(x))