Максимальная сумма подмассива с пропусками

Kotlin Сложный lists

Задача «Максимальная сумма подмассива с пропусками»

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

Формат ввода

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

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

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

Примеры

Пример 1

ВВОД

3
10 20 30

ВЫВОД

60

Пример 2

ВВОД

1 2 3

ВЫВОД

2

main.kt