Программирование Pearls: поиск подмассива с максимальной суммой

Question

Я читал книгу «Программирование жемчуга» и застрял в каком-то месте.(Лучшее) оригинальное решение проблемы (поиск подмассива с максимальной суммой):

maxsofar = О 
maxendinghere = О 
for i = [0. n) 
{
   maxendinghere = max(maxendinghere + x[i], 0) 
   maxsofar = max(maxsofar, maxendinghere) 
}

Затем проблема изменяется следующим образом, и программа запрашивается изменение:

Вместо того, чтобы находить подмассив с максимальной суммой, мы должны найти подмассив с ближайшей к нулю суммой ( не минимум) или каким-либо другим числом f .

1. Так что я бы решил эту проблему, просто изменив функцию " max " на некоторую функцию, которая будет возвращать число, которое ближе к нулю (или f).
2. maxsofar будет инициализирован элементом, ближайшим к нулю (или f)

Это решение работает в O (n), но автор дает решение, которое сложно и работает вO (nlogn) и утверждает, что это оптимальное решение (теоретически наилучшее из возможных).

Пожалуйста, не могли бы вы указать на ошибку в моем решении (если книга говорит, что nlogn является лучшим, то в моем решении должны быть некоторые ошибки).

ОБНОВЛЕНИЕ: Итак, мой ответ будет:

closest = get_element_closest_to_zero(); 
maxsofar = closest;
maxendinghere = 0; 
for i = [0. n) 
{
   maxendinghere = closest_to_zero(maxendinghere + x[i], closest);
   maxsofar = closest_to_zero(maxsofar, maxendinghere) ;
}

Спасибо.

Answer 1

Контрпример: [30; -50; 45]

Сначала вы выберете 30. Затем, когда вы доберетесь до -50, maxendinghere будет -20, а maxsofar также -20. Когда вы доберетесь до 45, у вас будет maxendinghere = closest(-20 + 45 = 25, 30) = 25, а maxsofar останется -20.

Однако правильный ответ -5: -50 + 45 = -5

Answer 2

Вот контрпример.

[100, 2, -2, -50]

Правильный ответ - подмассив [2, -2]. Однако, поскольку 100 + 2 - 2 == 100, а 100 + 2 - 2 - 50 = 50 и 50 ближе к 0, ваш алгоритм вернет [100, 2, -2, -50].

Answer 3

[1, 100, -100]

Для этого массива ваш алгоритм вернет [1], но правильный ответ должен быть [100, -100].

Answer 4

Как насчет последовательности [100, -201, 100].Это даст начальные условия

closest = 100
maxsofar = 100
maxendinghere = 0

после 1 шага

x[i] = 100
maxendinghere = closest_to_zero(100, 100)
maxsofar = 100

после 2 шагов

x[i] = -201
maxendinghere = closest_to_zero(-101, 100)
maxsofar = 100

после 3 шагов

x[i] = 100
maxendinghere = closest_to_zero(-101, 100)
maxsofar = 100