Задача #0538

Память 256 MB Время 1000 ms Сложность 50 %

Максимальная сумма

Вам дан массив a длины n. Ваша задача — найти максимальную сумму под-массива, которая может быть достигнута после выполнения следующей операции ровно один раз.

• Выберите любую часть массива из массива и установите значение всех элементов в нем равным 0.

Входные данные:

В первой строке вам задан число тестовых данных – t. (1 ≤ t ≤ 2*10⁴). В каждой из следующих t тестов:

В первой строке вам дам целое число n – длина массива. (1 ≤ n ≤ 5*10⁵)
Во второй строке вам дан n чисел – элементы массива. Элементы массива не превышают 10⁹.

Выходные данные:

Для каждого тестового примера выведите одно целое число – максимальную сумму под-массива.

Примеры

#	input.txt	output.txt
1	1 4 -1 4 -1 2	6

Telegram Facebook

Отправить решение

Пожалуйста, войдите в систему, чтобы выполнить это действие,если у вас нет учетной записи, вы можете зарегистрироваться в любое время