最大子数组和（允许删除一个元素）

Java Hard arrays

任务 «最大子数组和（允许删除一个元素）»

给定一个整数数组。需要找到子数组（连续元素序列）的最大和，条件是可以删除最多一个元素（或不删除任何元素）。子数组必须至少包含一个元素。要求实现时间复杂度为 O(n) 且使用常数额外空间的算法。

第一行包含一个整数 n (1 ≤ n ≤ 10^5) — 数组元素的数量。第二行包含 n 个由空格分隔的整数 — 数组元素（绝对值不超过 10^4）。

一个整数——删除不超过一个元素后子数组的最大可能和。

输入

5 1
1 2 3 2 4

输出

9

输入

2
7 1
-4 3

输出

8

输入

6
2 -1 2 3 4 -5

输出

11

main.java