Busca da soma máxima do subarray após deslocamento cíclico

Kotlin Hard loops

Tarefa «Busca da soma máxima do subarray após deslocamento cíclico»

Dado um array de números inteiros. É permitido realizar exatamente um deslocamento cíclico para a esquerda (o primeiro elemento se torna o último) ou para a direita (o último elemento se torna o primeiro) qualquer número de vezes, mas não mais que o comprimento do array. Após isso, é necessário encontrar a soma máxima do subarray contínuo (usando o algoritmo de Kadane). É necessário determinar a maior soma possível que pode ser obtida após realizar um deslocamento cíclico. Se o array estiver vazio, imprimir 0.

Formato de Entrada

Primeira linha: um inteiro N (1 ≤ N ≤ 10^6) — comprimento do array. Segunda linha: N números inteiros separados por espaços (cada um em módulo ≤ 10^9).

Formato de Saída

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

Exemplos

Exemplo 1

ENTRADA

4
-1 -2 -3 -4

SAÍDA

-1

main.kt