Поиск максимальной суммы подмассива с перестановками

C# Средний arrays

Задача «Поиск максимальной суммы подмассива с перестановками»

Дан массив целых чисел. Разрешается выполнить не более одной операции: выбрать два элемента массива и поменять их местами. Найдите максимальную возможную сумму непрерывного подмассива (любой длины, включая 0) после выполнения не более одной перестановки. Если сумма может быть отрицательной, выведите 0. Длина массива от 1 до 10^5, элементы от -10^4 до 10^4.

Формат ввода

Первая строка содержит целое число N — количество элементов массива. Вторая строка содержит N целых чисел через пробел.

Формат вывода

Одно целое число — максимальная сумма подмассива.

Примеры

Пример 1

ВВОД

3
-1 -2 -3

ВЫВОД

0

Пример 2

ВВОД

5
1 2 3 4 5

ВЫВОД

15

Пример 3

ВВОД

4
-1 2 3 -4

ВЫВОД

5

main.cs