Soma máxima de subarray com omissões

Kotlin Hard lists

Tarefa «Soma máxima de subarray com omissões»

Dada uma lista de números inteiros. É necessário encontrar a soma máxima de um subarray (sequência contínua de elementos), com a condição de que deste subarray pode-se remover no máximo um elemento (para obter uma soma maior). A remoção do elemento não é obrigatória. Se a lista estiver vazia, a soma é considerada 0. O comprimento da lista é de até 10^5, elementos de -10^4 a 10^4.

Formato de Entrada

A primeira linha contém um número inteiro N (1 ≤ N ≤ 100000) — a quantidade de elementos na lista. A segunda linha contém N números inteiros separados por espaços.

Formato de Saída

Um único número inteiro — a soma máxima possível do subarray após remover no máximo um elemento.

Exemplos

Exemplo 1

ENTRADA

3
10 20 30

SAÍDA

60

Exemplo 2

ENTRADA

1 2 3

SAÍDA

2

main.kt