A. Сумма-перевёртыш
ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
вводстандартный ввод
выводстандартный вывод
Вам дан массив из n
целых чисел a1,a2,…,an
. Каждое число равно либо 1
, либо −1
. Вы должны выполнить следующую операцию над массивом a
ровно один раз:
Выбрать индекс i
(1≤i<n
) и перевернуть знаки ai
и ai+1
. Здесь переворачивание знака означает, что −1
будет заменено на 1
, а 1
станет −1
.
Какое максимально возможное значение a1+a2+…+an
можно получить после применения вышеописанной операции?
Входные данные
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t
(1≤t≤500
) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого теста содержит одно целое число n
(2≤n≤105
) — длину массива a
.
Следующая строка содержит n
целых чисел a1,a2,…,an
(ai=1
либо ai=−1
).
Гарантируется, что сумма значений n
по всем наборам входных данных не превосходит 105
.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите максимально возможную сумму массива a
, которую вы можете получить в результате применения одной операции.
Пример
входные данныеСкопировать
4
5
-1 1 1 -1 -1
5
1 1 -1 -1 -1
2
1 1
4
1 -1 -1 1
выходные данныеСкопировать
3
3
-2
4
Примечание
В первом случае мы можем выбрать индекс 4
и перевернуть знаки a4
и a5
. После этой операции сумма будет равна −1+1+1+1+1=3
. Можно показать, что мы не можем сделать сумму больше этого значения.
В третьем наборе единственным вариантом является выбор индекса 1
.
ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
вводстандартный ввод
выводстандартный вывод
Вам дан массив из n
целых чисел a1,a2,…,an
. Каждое число равно либо 1
, либо −1
. Вы должны выполнить следующую операцию над массивом a
ровно один раз:
Выбрать индекс i
(1≤i<n
) и перевернуть знаки ai
и ai+1
. Здесь переворачивание знака означает, что −1
будет заменено на 1
, а 1
станет −1
.
Какое максимально возможное значение a1+a2+…+an
можно получить после применения вышеописанной операции?
Входные данные
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t
(1≤t≤500
) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого теста содержит одно целое число n
(2≤n≤105
) — длину массива a
.
Следующая строка содержит n
целых чисел a1,a2,…,an
(ai=1
либо ai=−1
).
Гарантируется, что сумма значений n
по всем наборам входных данных не превосходит 105
.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите максимально возможную сумму массива a
, которую вы можете получить в результате применения одной операции.
Пример
входные данныеСкопировать
4
5
-1 1 1 -1 -1
5
1 1 -1 -1 -1
2
1 1
4
1 -1 -1 1
выходные данныеСкопировать
3
3
-2
4
Примечание
В первом случае мы можем выбрать индекс 4
и перевернуть знаки a4
и a5
. После этой операции сумма будет равна −1+1+1+1+1=3
. Можно показать, что мы не можем сделать сумму больше этого значения.
В третьем наборе единственным вариантом является выбор индекса 1
.