Suma máxima del subarreglo con eliminación de un elemento

Java Hard arrays

Tarea «Suma máxima del subarreglo con eliminación de un elemento»

Dado un arreglo de enteros. Es necesario encontrar la suma máxima de un subarreglo (secuencia continua de elementos) con la condición de que se pueda eliminar no más de un elemento (o no eliminar ninguno). El subarreglo debe contener al menos un elemento. Se requiere implementar un algoritmo con complejidad temporal O(n) y memoria adicional constante.

Formato de entrada

La primera línea contiene un entero n (1 ≤ n ≤ 10^5) — la cantidad de elementos del arreglo. La segunda línea contiene n enteros separados por espacios — los elementos del arreglo (cuyo valor absoluto no supera 10^4).

Formato de salida

Un solo entero — la suma máxima posible del subarreglo después de eliminar no más de un elemento.

Ejemplos

Ejemplo 1

ENTRADA

5 1
1 2 3 2 4

SALIDA

9

Ejemplo 2

ENTRADA

2
7 1
-4 3

SALIDA

8

Ejemplo 3

ENTRADA

6
2 -1 2 3 4 -5

SALIDA

11

main.java