Suma máxima de un subarreglo con omisiones

Kotlin Hard lists

Tarea «Suma máxima de un subarreglo con omisiones»

Dada una lista de números enteros. Es necesario encontrar la suma máxima de un subarreglo (secuencia continua de elementos), bajo la condición de que de este subarreglo se pueda eliminar como máximo un elemento (para obtener una suma mayor). La eliminación del elemento no es obligatoria. Si la lista está vacía, la suma se considera igual a 0. La longitud de la lista es de hasta 10^5, los elementos van de -10^4 a 10^4.

Formato de entrada

La primera línea contiene un número entero N (1 ≤ N ≤ 100000) — la cantidad de elementos en la lista. La segunda línea contiene N números enteros separados por espacios.

Formato de salida

Un número entero — la suma máxima posible del subarreglo después de eliminar como máximo un elemento.

Ejemplos

Ejemplo 1

ENTRADA

3
10 20 30

SALIDA

60

Ejemplo 2

ENTRADA

1 2 3

SALIDA

2

main.kt