Soma Máxima de Subarray com Deslocamento Cíclico

PHP Hard arrays

Tarefa «Soma Máxima de Subarray com Deslocamento Cíclico»

Dado um array de números inteiros. É necessário encontrar a soma máxima de um subarray (sequência contínua de elementos) após aplicar exatamente um deslocamento cíclico para a esquerda por um número arbitrário de posições (de 0 a N-1). Se após o deslocamento o subarray puder ser vazio, a soma do subarray vazio é considerada igual a 0. O subarray deve conter pelo menos um elemento, se todos os elementos forem negativos. Restrições: comprimento do array de 1 a 10^5, elementos de -10^9 a 10^9.

Formato de Entrada

A primeira linha contém um número inteiro N (1 ≤ N ≤ 100000) — o tamanho do array. A segunda linha contém N números inteiros — os elementos do array.

Formato de Saída

Um número inteiro — a soma máxima do subarray após um deslocamento cíclico para a esquerda.

Exemplos

Exemplo 1

ENTRADA

5

SAÍDA

10

Exemplo 2

ENTRADA

-3

SAÍDA

-6

main.php