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

PHP Сложный arrays

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

Дан массив целых чисел. Необходимо найти максимальную сумму подмассива (непрерывной последовательности элементов) после применения ровно одного циклического сдвига влево на произвольное количество позиций (от 0 до N-1). Если после сдвига подмассив может быть пустым, то сумма пустого подмассива считается равной 0. Подмассив должен содержать хотя бы один элемент, если все элементы отрицательные. Ограничения: длина массива от 1 до 10^5, элементы от -10^9 до 10^9.

Формат ввода

Первая строка содержит целое число N (1 ≤ N ≤ 100000) — размер массива. Вторая строка содержит N целых чисел — элементы массива.

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

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

Примеры

Пример 1

ВВОД

5

ВЫВОД

10

Пример 2

ВВОД

-3

ВЫВОД

-6

main.php