寻找最大子数组和，考虑负元素和循环移位

TypeScript Hard loops

任务 «寻找最大子数组和，考虑负元素和循环移位»

给定一个整数数组。需要找到在执行最多一次向左或向右的循环移位后，子数组（连续元素序列）的最大和。循环移位意味着元素像在圆环上一样移动。如果不进行移位，则从原始数组中选择子数组。如果进行移位，则可以从移位后的数组中选择子数组。输出最大可能的和。数组长度从1到10^5，元素范围从-10^4到10^4。使用考虑循环移位的Kadane算法。

输入格式

第一行包含一个整数N——数组的元素数量。第二行包含N个整数，以空格分隔。

输出格式

一个整数——子数组的最大和。

示例

示例 1

输入

3
10 -5 10

输出

20

示例 2

输入

7
abacaba
2
3

输出

2
aba
acb

main.ts