通过交换求最大子数组和

C# Medium 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