Soma máxima do subarray com remoção de um elemento

Java Hard arrays

Tarefa «Soma máxima do subarray com remoção de um elemento»

Dado um array de inteiros. É necessário encontrar a soma máxima do subarray (sequência contínua de elementos) com a condição de que seja possível remover no máximo um elemento (ou não remover nenhum). O subarray deve conter pelo menos um elemento. É necessário implementar um algoritmo com complexidade de tempo O(n) e memória adicional constante.

Formato de Entrada

A primeira linha contém um número inteiro n (1 ≤ n ≤ 10^5) — a quantidade de elementos do array. A segunda linha contém n números inteiros, separados por espaços — os elementos do array (em módulo não excedem 10^4).

Formato de Saída

Um número inteiro — a soma máxima possível do subarray após a remoção de no máximo um elemento.

Exemplos

Exemplo 1

ENTRADA

5 1
1 2 3 2 4

SAÍDA

9

Exemplo 2

ENTRADA

2
7 1
-4 3

SAÍDA

8

Exemplo 3

ENTRADA

6
2 -1 2 3 4 -5

SAÍDA

11

main.java