Здравствуйте, subdmitry, Вы писали:

S>Это не верно. Контрпример — возьмем X=1 и a={11 -3}. Схема генерации с минимальным вылетом вверх получается такая (числа в скобках это временная сумма): 11 -3 -3 -3 (2) 11 (13) -3 -3 -3 -3 (1). То есть вылет получается на 13, что больше X+max(ai)=1+11=12. Видно, что сделать вылет меньше нельзя. Вопрос о том, что брать как верхнюю грань, отсекающую лишний поиск, не так прост. Ну, кто сообразит, сколько тут должно быть? Я как следующее предположение рискну выдвинуть |X|+sum|ai|.

Нашел. Для максимального по модулю вылета (и ограничении снизу 0-м) годится оценка в |Х|+|mах(-ai)|+|max(ai)|. То есть сумма модуля максимально отрицательного элемента и максимального положительного.