Не могу решить задачку по алгоритмам

[Laguna]

Доброго времени суток, господа! Столкнулся со следующей задачей:
"Мощностью элемента назовем сумму максимального элемента, стоящего справа от него, и максимального элемента, стоящего от него слева. Мощность крайних элементов будем считать равной 0. У вас имеется первоначально пустой массив, к которому по очереди справа приписываются n целых чисел. На каждом шаге посчитайте и выведите наибольшее значение среди мощностей его элементов.
Формат ввода:
В первой строке входных данных записано целое число n ($3 \leqslant$ $n$ $\leqslant 10^6$).
Во второй строке записаны n целых чисел a_i($-10^9 \leqslant$ $a_i$ $\leqslant 10^9$) - последовательно добавляющиеся в массив элементы.
Формат вывода:
В качестве ответа выведите n целых чисел - наибольшие мощности на каждом из n шагов.
Пример 1:
Ввод:
3
1 3 4
Вывод:
0 0 6
Пример 2:
Ввод:
4
2 3 3 2
Вывод:
0 0 5 5"
Я придумал такое решение. Будем использовать невозрастающую бинарную кучу. До начала основного цикла запушим в кучу первые 2 элемента, а также выведем 2 нуля(первые 2 элемента, очевидно, всегда нули). Идея моего алгоритма заключается в том, что по факту, мы хотим найти сумму двух самых больших элементов текущей кучи, однако просто выводить сумму максимального и пред-максимального не получится, ибо они могут стоять рядом, а тогда это не прокатывает. Если эти элементы стоят рядом, найдем пред-пред-максимальный элемент, и, если он не стоит рядом с максимальным, то выведем сумму его и максимального, а если стоит, то выведем сумму пред-максимального и пред-пред-максимального. Там еще надо написать условие, что если, вдруг, максимальная сумма отрицательна, то надо выводить просто 0. Ну а дальше запускаем цикл, который на каждой итерации закидывает новый элемент в кучу, проверяет условия выше и выдает ответ. Я проверил этот алгоритм на парочке тестов и все было норм, пока сегодня, сидя на скучной паре в университете, в голову не пришел контрпример, показывающий неправильность моего алгоритма. Контрпример такой: На входе массив (198, 200, 800, 199). Правильным ответом должна быть последовательность 0 0 998 998, а мой алгоритм выдает 0 0 998 399. Я думаю, что можно это поправить, добавив поиск пред-пред-пред-максимального элемента, однако, как мне кажется, это уже чересчур громоздко. Кто-нибудь знает, как можно по-нормальному без костылей решить эту задачу? Быть может здесь можно как-то воспользоваться тем условием, что выходная последовательность неубывает?

[mihaild]

А откуда в первом примере шестерка? У нас есть только один элемент не на краю, это тройка, слева от неё 1, справа 4, в сумме 5.

Вроде бы достаточно помнить 4 наибольших (и кстати куча для этого не нужна).
Обозначим $x_1, x_2, x_3, x_4$ четверку наибольших на текущий момент. Наибольшая возможная сумма $x_1 + x_2$, дальше $x_1 + x_3$, если они обе невозможны из-за соседства, то возможны $x_2 + x_3$ и $x_1 + x_4$, и берем максимальную из них.

[ozheredov]

Laguna в сообщении #1634803 писал(а):

Ввод:
3
1 3 4
Вывод:
0 0 6

Мощность крайних элементов 1 и 4 равна нулю, но почему мощность среднего-то 6, если $1 + 4 = 5$?
UPD: опередили )

[Laguna]

mihaild в сообщении #1634806 писал(а):

А откуда в первом примере шестерка? У нас есть только один элемент не на краю, это тройка, слева от неё 1, справа 4, в сумме 5.

Да, Вы правы, это я опечатался, там должно быть 1 4 5. Я бы исправил мое сообщение, да только что-то не вижу как .

-- 30.03.2024, 14:59 --

mihaild в сообщении #1634806 писал(а):

Вроде бы достаточно помнить 4 наибольших (и кстати куча для этого не нужна).
Обозначим $x_1, x_2, x_3, x_4$ четверку наибольших на текущий момент. Наибольшая возможная сумма $x_1 + x_2$, дальше $x_1 + x_3$, если они обе невозможны из-за соседства, то возможны $x_2 + x_3$ и $x_1 + x_4$, и берем максимальную из них.

А как это можно красиво сделать? Первое, что приходит на ум, это если входной массив по длине равен тройке, то перебрать все суммы и вывести, а если по длине он больше или равен четырем, то вручную вычислить 4 максимальных элемента и поставить указатели на них, и каждый раз, когда добавляется новый элемент, делать 4 проверки, и менять указатели, после чего искать максимальную сумму элементов среди этих 4-х, которые не стоят рядом

[mihaild]

Laguna в сообщении #1634851 писал(а):

А как это можно красиво сделать?

Делаем отдельно структуру с операциями "добавить новый элемент", "получить 4 максимальных элемента из ранее добавленных". Реализуется как массив размера 4, который храним отсортированным, и при добавлении нового элемента сравниваем его с последним в массиве, если больше - то заменяем последний элемент в массиве на наш, и делаем итерацию пузырька.