|
2010-2011
|
Занимательная математика (100 баллов)
Вова является одним из самых прилежных учеников в своем классе. Самым любимым для Вовы предметом является математика. Совсем недавно Вова на уроке математики изучал тему «Модуль целого числа». Тема показалась Вове очень простой и он как всегда попросил у учителя дополнительное задание повышенной сложности. Учитель предложил ему непростую задачку:
Дана
последовательность целых чисел A1, A2, … , AN-1, AN., из которой необходимо
выбрать такую подпоследовательность, что сумма всех модулей чисел, входящих в
данную подпоследовательноть, прибавленная к сумме чисел входящих в
подпоследовательность была максимальной. Подпоследовательностью
последовательности Ai будем называть любую последовательность вида Ai, Ai+1, …,
Aj для любых i и j, удовлетворяющих условию Например, дана последовательность из пяти чисел: -3 5 -10 8 -2. Из условия задачи следует, что необходимо выбрать такую подпоследовательность, чтобы сумма всех модулей чисел этой подпоследовательности, прибавленная к сумме чисел подпоследовательности, была максимальна. Существует много вариантов выбора, однако подпоследовательность, состоящая из чисел 5 -10 8, является искомой, так как (|5| + |-10| + |8|) + (5 + (-10) + 8) = 26 – максимально возможная сумма. Ваша задача – помочь отличнику Вове в решении эту непростой задачи. Входные данные Первая строка входного файла содержит одно целое число N (1 ≤ N ≤ 1000). Вторая строка содержит N целых чисел Ai (-106 ≤ Ai ≤ 106), разделенных одиночными пробелами. Выходные данные Выходной файл должен содержать одно целое число – максимально возможную сумму.
|