Suma máxima de subarreglo con desplazamiento cíclico

PHP Hard arrays

Tarea «Suma máxima de subarreglo con desplazamiento cíclico»

Dado un arreglo de números enteros. Es necesario encontrar la suma máxima de un subarreglo (secuencia continua de elementos) después de aplicar exactamente un desplazamiento cíclico hacia la izquierda en una cantidad arbitraria de posiciones (de 0 a N-1). Si después del desplazamiento el subarreglo puede estar vacío, entonces la suma del subarreglo vacío se considera igual a 0. El subarreglo debe contener al menos un elemento si todos los elementos son negativos. Restricciones: longitud del arreglo de 1 a 10^5, elementos de -10^9 a 10^9.

Formato de entrada

La primera línea contiene un número entero N (1 ≤ N ≤ 100000) — el tamaño del arreglo. La segunda línea contiene N números enteros — los elementos del arreglo.

Formato de salida

Un número entero — la suma máxima del subarreglo después de un desplazamiento cíclico hacia la izquierda.

Ejemplos

Ejemplo 1

ENTRADA

5

SALIDA

10

Ejemplo 2

ENTRADA

-3

SALIDA

-6

main.php