Поиск максимальной суммы подмассива после циклического сдвига

Kotlin Сложный loops

Задача «Поиск максимальной суммы подмассива после циклического сдвига»

Дан массив целых чисел. Разрешается выполнить ровно один циклический сдвиг влево (первый элемент становится последним) или вправо (последний элемент становится первым) любое количество раз, но не более длины массива. После этого необходимо найти максимальную сумму непрерывного подмассива (с использованием алгоритма Кадане). Требуется определить наибольшую возможную сумму, которую можно получить после выполнения одного циклического сдвига. Если массив пустой, вывести 0.

Формат ввода

Первая строка: целое число N (1 ≤ N ≤ 10^6) — длина массива. Вторая строка: N целых чисел, разделённых пробелами (каждое по модулю ≤ 10^9).

Формат вывода

Одно целое число — максимальная сумма подмассива после одного циклического сдвига.

Примеры

Пример 1

ВВОД

4
-1 -2 -3 -4

ВЫВОД

-1

main.kt