Вам дан массив a
из n
целых чисел. Вы должны выполнить следующие две операции с массивом (сначала первую, затем вторую):
Произвольно переставить элементы массива или оставить порядок его элементов без изменений.
Выбрать не более одного отрезка подряд идущих элементов и заменить знаки всех элементов на этом отрезке на противоположные. Формально, вы можете выбрать пару индексов l,r
такие, что 1≤l≤r≤n
и присвоить ai=−ai
для всех l≤i≤r
. Заметим, что вы можете не выбирать пару индексов и оставить все знаки элементов без изменений.
Какова максимальная сумма элементов массива после последовательного выполнения двух операций (сначала первой, затем второй)?
Входные данные
Первая строка входных данных содержит одно целое число t
(1≤t≤1000
) — количество наборов входных данных. Затем следуют описания наборов.
Первая строка каждого набора входных данных содержит одно целое число n
(1≤n≤50
) — количество элементов в массиве a
.
Вторая строка каждого набора входных данных содержит n
целых чисел a1,a2,…,an
(−100≤ai≤100
) — элементы массива.
Выходные данные
Для каждого набора входных данных выведите максимальную сумму элементов массива после последовательного выполнения двух заданных операций.Примечание
В первом наборе входных данных вы можете сначала переставить массив, чтобы получился [3,−2,−3]
(операция 1), затем выбрать l=2,r=3
и получить сумму 3+−((−2)+(−3))=8
(операция 2).
Во втором наборе входных данных вы можете ничего не делать при выполнении обеих операций и получить сумму 0
.
В третьем наборе входных данных вы можете ничего не делать при выполнении обеих операций и получить сумму 0+1=1
.
В четвертом наборе входных данных вы можете сначала оставить порядок неизменным (операция 1), затем выбрать l=1,r=1
и получить сумму −(−99)=99
(операция 2).
В пятом наборе входных данных вы можете сначала оставить порядок неизменным (операция 1), затем выбрать l=2,r=3
и получить сумму 10+−((−2)+(−3))+7=22
(операция 2).
В шестом наборе входных данных вы можете сначала оставить порядок неизменным (операция 1), затем выбрать l=1,r=5
и получить сумму −((−1)+(−2)+(−3)+(−4)+(−5))=15
(операция 2).