Задача с максимальной суммой подмассива имеет очень простое линейное временное решение https://en.m.wikipedia.org/wiki/Maximum_subarray_problem.
Если вместо этого мы хотим максимизировать сумму (подмассив)/sqrt (длину подмассива), есть ли субквадратичное временное решение?
Элементы входного массива будут значениями с плавающей запятой в диапазоне от -infinity до +infinity.
Я добавил версию кода, основанного на Kadane, для тестирования ниже. Кажется, в моем тестировании разница до 10% (запустите сниппет для случайных тестов).
(Конец обновления)
Лучшее, что я смог придумать в качестве приблизительного значения, - это двоичный поиск по цели со случайными выборками размера окна во время поиска O(log m * n * num_samples_constant), где m - диапазон. В тестировании я видел разницу между грубой силой (ограничена массивом 5000 элементов, в диапазоне ± 1000000000), а последние варьируются от 0 до 30% при размере выборки 200 длин окон. (Может быть, еще одна рутина может уточнить?)
Приведенный ниже код JavaScript запускает 10 тестов и сообщает о самых маленьких и самых больших разностях, а затем просто бинарный поиск по более длинному массиву.
Другие мысли включали использование БПФ для генерации сумм, но я не знаю, может ли быть эффективный способ соотнести каждую сумму с длиной подмассива, которая ее сгенерировала; а также пытаясь найти другое представление о проблеме:
f = sqrt(i - j) * (si - sj), for j < i
f^2 = sqrt(i - j) * (si - sj) * sqrt(i - j) * (si - sj)
= (i - j) * (si^2 - 2si*sj + sj^2)
= i*si^2 - 2i*si*sj + i*sj^2
-j*si^2 + 2j*si*sj - j*sj^2
= i*si^2 +
(-2sj, sj^2, -j, 2j*sj, -j*sj^2) // known before i
dot (i*si, 1, si^2, si, 1)
(Таким образом, если бы мы решили 5-мерное обновление выпуклой оболочки во время регистрации, 5-мерную проблему экстремальных точек и выяснили, был ли наш кандидат положительным или отрицательным, мы были бы хороши, чтобы пойти :)
function prefix_sums(A){
let ps = new Array(A.length + 1).fill(0)
for (let i=0; i<A.length; i++)
ps[i + 1] = A[i] + ps[i]
return ps
}
function brute_force(ps){
let best = -Infinity
let best_idxs = [-1, -1]
for (let i=1; i<ps.length; i++){
for (let j=0; j<i; j++){
let s = (ps[i] - ps[j]) / Math.sqrt(i - j)
if (s > best){
best = s
best_idxs = [j, i - 1]
}
}
}
return [best, best_idxs]
}
function get_high(A){
return A.reduce((acc, x) => x > 0 ? acc + x : acc, 0)
}
function get_low(A){
return Math.min.apply(null, A)
}
function f(A){
let n = A.length
let ps = prefix_sums(A)
let high = get_high(A)
let low = get_low(A)
let best = [-1, -1]
let T = low + (high - low) / 2
let found = false
while (low + EPSILON < high){
T = low + (high - low) / 2
// Search for T
found = false
for (let l=0; l<NUM_SAMPLES; l++){
let w = Math.max(1, ~~(Math.random() * (n + 1)))
for (let i=w; i<ps.length; i++){
let s = (ps[i] - ps[i - w]) / Math.sqrt(w)
if (s >= T){
found = true
best = [i - w, i - 1]
break
}
}
if (found)
break
}
// Binary search
if (found)
low = T
else
high = T - EPSILON
}
return [low, best]
}
function max_subarray(A){
var max_so_far = max_ending_here = A[0]
var startOld = start = end = 0
var divb = divbo = 1
//for i, x in enumerate(A[1:], 1):
for (let i=1; i<A.length; i++){
var x = A[i]
divb = i - start + 1
divbo = divb - 1
if (divb <= 1){
divb = 1
divbo = 1
}
undo = max_ending_here * Math.sqrt(divbo)
max_ending_here = Math.max(x, (undo + x)/Math.sqrt(divb))
if (max_ending_here == x)
start = i
max_so_far = Math.max(max_so_far, max_ending_here)
if (max_ending_here < 0)
start = i + 1
else if (max_ending_here == max_so_far){
startOld = start
end = i
}
}
if (end == A.length-1){
start = startOld + 1
var new_max = max_so_far
divbo = end - startOld + 1
divb = divbo - 1
while (start < end){
new_max = (new_max * Math.sqrt(divbo) - A[start-1])/Math.sqrt(divb)
if (new_max > max_so_far){
max_so_far = new_max
startOld = start
}
start += 1
}
}
return [max_so_far , startOld, end]
}
const EPSILON = 1
const NUM_SAMPLES = 200
let m = 1000000000
let n = 5000
let A
let max_diff = 0
let min_diff = Infinity
let max_diff2 = 0
let min_diff2 = Infinity
let num_tests = 10
for (let i=0; i<num_tests; i++){
A = []
for (let i=0; i<n; i++)
A.push([-1, 1][~~(2 * Math.random())] * Math.random() * m + Math.random())
let f_A = f(A)
let g_A = brute_force(prefix_sums(A))
let m_A = max_subarray(A)
let diff = (g_A[0] - f_A[0]) / g_A[0]
max_diff = Math.max(max_diff, diff)
min_diff = Math.min(min_diff, diff)
let diff2 = (g_A[0] - m_A[0]) / g_A[0]
max_diff2 = Math.max(max_diff2, diff2)
min_diff2 = Math.min(min_diff2, diff2)
}
console.log('${ n } element array')
console.log('${ num_tests } tests')
console.log('min_diff: ${ min_diff * 100 }%')
console.log('max_diff: ${ max_diff * 100 }%')
console.log('min_diff (Kadane): ${ min_diff2 * 100 }%')
console.log('max_diff (Kadane): ${ max_diff2 * 100 }%')
n = 100000
A = []
for (let i=0; i<n; i++)
A.push([-1, 1][~~(2 * Math.random())] * Math.random() * m + Math.random())
var start = +new Date()
console.log('\n${ n } element array')
console.log(JSON.stringify(f(A)))
console.log('${ (new Date() - start) / 1000 } seconds')Интересная проблема. Поскольку вы упомянули интерес к аппроксимациям, здесь представлена схема аппроксимации 1-O (ε), которая выполняется за время O (nε- 1). Он обладает хорошим свойством использования только + и max, обходя проблему катастрофической отмены, вызванную вычитанием сумм префиксов. (Поскольку входные данные содержат отрицательные числа, все еще возможно получить катастрофическое аннулирование, но тогда мы можем согласиться на подмассив, содержащий только большое положительное целое число.)
Пусть k = ceil (ε − 1). За O (nε − 1) время мы можем оценить каждый подмассив длины между 1 и k, используя простой алгоритм. Мы оцениваем более длинные подмассивы приближенным способом, итеративно огрубляя входные данные и выполняя в основном тот же алгоритм. Поскольку входное значение уменьшается на постоянный коэффициент в каждой итерации, общее время работы составляет O (nε − 1).
Процедура укрупнения работает следующим образом. Мы сохраняем три производных массива одинаковой длины. Каждая позиция в производных массивах соответствует подмассиву длиной 2 ℓ в исходном вводе. Три полученных массива: S (каждый элемент является максимальной суммой суффикса соответствующего подмассива), A (каждый элемент является суммой соответствующего подмассива) и P (каждый элемент является максимальной суммой префикса соответствующего подмассива). Рассматривая S [i] + A [i + 1] +… + A [j − 1] + P [j] для некоторого я <j, мы имеем максимальную сумму подмассива входных данных, которая начинается в подмассиве, соответствующем положение я и заканчивается в подмассиве, соответствующем положению j. Длина подмассива, достигающего этой суммы, находится между 2 ℓ (j − я − 1) + 2 и 2 ℓ (j − я + 1). Этого достаточно, чтобы ограничить цель (если сумма является положительной, использовать последнюю в качестве оценки для числа элементов; если сумма является отрицательной, использовать первую) и, таким образом, может приблизительно сравнить ее с другими подмассивами.
Чтобы вывести S ′, A ′, P ′ из S, A, P на каждой итерации, мы вычисляем S ′ [i] = max (S [2i] +A [2i + 1], S [2i + 1]) и A ′ [i] = A [2i] + A [2i + 1] и P ′ [i] = max (P [2i], A [2i] + P [2i + 1]). Если индекс 2i существует, а 2i + 1 нет, мы устанавливаем S ′ [2i] = S [2i] и A ′ [2i] = A [2i] и P ′ [2i] = P [2i].
Эскиз доказательства аппроксимации 1 − O (ε) состоит в том, что при оптимальном подмассиве мы находим наименьшее ℓ такое, что его длина не превышает 2 ℓ − 1 k. Затем мы смотрим на итерацию ℓ, находим я и j и наблюдаем, что S [i] + A [i + 1] +… + A [j − 1] + P [j], по крайней мере, равна сумме оптимальный подрешетку, и связать потери, понесенные путем округления знаменателя с мультипликативным множителем 1 + O (ε).
Алгоритм Кадане (второй показывает отслеживание начала и конца подмассива), показанный на этой странице википедии, также должен работать для этого, так как (a + b)/sqrt (n) совпадает с /sqrt (n) + b/sqrt (п). Таким образом, вместо добавления полного значения (max_end_here + x) вы должны отменить предыдущее деление, добавить новое значение и затем разделить на квадратный корень новой длины.
import math
def max_subarray(A):
max_so_far = max_ending_here = A[0]
startOld = start = end = 0
divb = divbo = 1
for i, x in enumerate(A[1:], 1):
divb = i - start + 1
divbo = divb - 1
if divb <= 1:
divb = 1
divbo = 1
undo = max_ending_here * math.sqrt(divbo)
max_ending_here = max(x, (undo + x)/math.sqrt(divb))
if max_ending_here == x: # reset when a single number is larger than previous max subarray
start = i
max_so_far = max(max_so_far, max_ending_here)
if max_ending_here < 0:
start = i + 1
elif max_ending_here == max_so_far:
startOld = start
end = i
# check if shortening increases max
start = startOld + 1
new_max = max_so_far
divbo = end - startOld + 1
divb = divbo - 1
while (start < end):
new_max = (new_max * math.sqrt(divbo) - A[start-1])/math.sqrt(divb)
if new_max > max_so_far:
max_so_far = new_max
startOld = start
start += 1
divb -= 1
divbo -= 1
if divb < 1:
break
return (max_so_far , startOld, end)
a = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(a)
print(max_subarray(a))
a = [1, 2, 3, 4, -1, 2, 1, -5, 4]
print(a)
print(max_subarray(a))
a = [-571218039.35953,993870065.9750855,520554093.5890911,336453508.124072,341730314.3580449]
print(a)
print(max_subarray(a))
a = [993870065.9750855,-571218039.35953,520554093.5890911,336453508.124072,341730314.3580449]
print(a)
print(max_subarray(a))
a = [903293995.5092816, -446822629.61604935, -441981815.2268512, 918327233.3661327, -172699078.33198473]
print(a)
print(max_subarray(a))
a = [-627703132.0023746,-269316542.4622296,267057965.81026044,568764120.4442698,767020098.5785978]
print(a)
print(max_subarray(a))
