Задача . C. Прекрасная рандомизированная сумма

Учиться, учиться и еще раз учиться — вот чем приходится заниматься Валере каждый будний день. Он учится в математической школе, где конечно же профильным предметом является математика. Учительница математики Валерия Валерьевна очень любит свой предмет и всячески пытается привить эту любовь ученикам. Однако её методы весьма сомнительны, так как ради достижения своей цели она постоянно дает детям очень объемные и сложные домашние задания. Несмотря на то что Валера вовсе не худший ученик в классе, с очередным домашним заданием, которое как всегда оказалось непростым, он не справился. Вот поэтому он и обратился к Вам за помощью. А задание у Валеры такое: пусть задана последовательность из n чисел. Назовем префиксом последовательности некоторое количество первых ее элементов (возможно нулевое), а суффиксом — некоторое количество последних ее элементов (возможно нулевое). Разрешается последовательно выполнить две операции - взять произвольный префикс последовательности и умножить все числа в нем на  - 1, а затем проделать такую же операцию с суффиксом (префикс и суффикс могут пересекаться). Какую наибольшую сумму элементов последовательности можно получить в результате этих двух действий?