Recherche de la somme maximale d’un sous-tableau après un décalage circulaire

Kotlin Hard loops

Tâche «Recherche de la somme maximale d’un sous-tableau après un décalage circulaire»

Un tableau d’entiers est donné. Il est permis d’effectuer exactement un décalage circulaire vers la gauche (le premier élément devient le dernier) ou vers la droite (le dernier élément devient le premier) un nombre quelconque de fois, mais pas plus que la longueur du tableau. Ensuite, il faut trouver la somme maximale d’un sous-tableau continu (en utilisant l’algorithme de Kadane). Il est nécessaire de déterminer la plus grande somme possible pouvant être obtenue après avoir effectué un seul décalage circulaire. Si le tableau est vide, afficher 0.

Format d\ entrée

Première ligne : un entier N (1 ≤ N ≤ 10^6) — la longueur du tableau. Deuxième ligne : N entiers séparés par des espaces (chacun en valeur absolue ≤ 10^9).

Format de sortie

Un seul entier — la somme maximale du sous-tableau après un seul décalage circulaire.

Exemples

Exemple 1

ENTRÉE

4
-1 -2 -3 -4

SORTIE

-1

main.kt