Somme maximale d'un sous-tableau avec suppression d'un élément

Java Hard arrays

Tâche «Somme maximale d'un sous-tableau avec suppression d'un élément»

Étant donné un tableau d'entiers. Il faut trouver la somme maximale d'un sous-tableau (séquence continue d'éléments) à condition que l'on puisse supprimer au plus un élément (ou ne supprimer aucun élément). Le sous-tableau doit contenir au moins un élément. Il est requis d'implémenter un algorithme avec une complexité temporelle O(n) et une mémoire supplémentaire constante.

Format d\ entrée

La première ligne contient un entier n (1 ≤ n ≤ 10^5) — le nombre d'éléments du tableau. La deuxième ligne contient n entiers séparés par des espaces — les éléments du tableau (leur valeur absolue ne dépasse pas 10^4).

Format de sortie

Un entier — la somme maximale possible du sous-tableau après la suppression d'au plus un élément.

Exemples

Exemple 1

ENTRÉE

5 1
1 2 3 2 4

SORTIE

9

Exemple 2

ENTRÉE

2
7 1
-4 3

SORTIE

8

Exemple 3

ENTRÉE

6
2 -1 2 3 4 -5

SORTIE

11

main.java