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

Дан массив целых чисел. Необходимо найти максимальную сумму подмассива (непрерывной последовательности элементов) после выполнения не более одного циклического сдвига массива влево или вправо. Циклический сдвиг означает, что элементы перемещаются, как по кругу. Если сдвиг не производится, то подмассив выбирается из исходного массива. Если сдвиг производится, то подмассив может быть выбран из массива после сдвига. Вывести максимальную возможную сумму. Длина массива от 1 до 10^5, элементы от -10^4 до 10^4. Использовать алгоритм Кадане с учетом циклического сдвига.

Пример 1

Пример 2