Максимальная сумма подмассива с удалением одного элемента

Java Сложный arrays

Задача «Максимальная сумма подмассива с удалением одного элемента»

Дан целочисленный массив. Необходимо найти максимальную сумму подмассива (непрерывной последовательности элементов) при условии, что можно удалить не более одного элемента (или не удалять ни одного). Подмассив должен содержать хотя бы один элемент. Требуется реализовать алгоритм с временной сложностью O(n) и константной дополнительной памятью.

Формат ввода

Первая строка содержит целое число n (1 ≤ n ≤ 10^5) — количество элементов массива. Вторая строка содержит n целых чисел, разделённых пробелами — элементы массива (по модулю не превышают 10^4).

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

Одно целое число — максимальная возможная сумма подмассива после удаления не более одного элемента.

Примеры

Пример 1

ВВОД

5 1
1 2 3 2 4

ВЫВОД

9

Пример 2

ВВОД

2
7 1
-4 3

ВЫВОД

8

Пример 3

ВВОД

6
2 -1 2 3 4 -5

ВЫВОД

11

main.java