化环为直

将数组复制一个粘到原数组后面，并保证子数组长度小于原数组长度，即转化为可变长滑动窗口最大值
可变长滑动窗口的长度在[1,n]闭区间
1，-2，3，-2 将环展开为2n长度的数组
变为[1，-2，3，-2, 1，-2，3，-2]

利用前缀和快速求窗口最大值

先求出所有前缀和：前缀和数组第i个值为原数组从第0到i索引的元素总和
给定一个终点，比如[1，-2，3，-2, 1，-2，3，-2]中的第二个1'
则以1’为终点的所有长度不超过4的区间的元素和=`s[i]- s[j]`,i为1‘对应在前缀和数组中的索引
s为前缀和数组，j为子区间的左边界索引，保证`i-j <= 4`，子区间元素索引为`[j+1,j+2,...,i]`

要让子区间元素总和最大，即s[i]-s[j]最大，
因为s[i]为固定值，其实就是找j,使得s[j]最小

所以滑动窗口其实是在前缀和数组中滑动的
维护单调上升的队列，队头是最小元素，即最小的前缀和终点 

Py代码

from collections import deque
class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:
        n = len(A)
        # 将数组复制一个粘到原数组后面
        for i in range(n): A.append(A[i])
        # 生成前缀和数组，下标从1开始，这样生成第一个前缀和不用特判越界
        sum = [0 for i in range(2 * n + 1)]
        for i in range(1, 2 * n + 1):
            sum[i] = sum[i - 1] + A[i - 1]

        res = -float('inf')
        q = deque()
        q.append(0) # 加入前缀和数组第一个元素索引0
        i = 1
        while i < len(sum):
            # 队头在最长窗口左边，删除队头，表示该队头不能作为求子区间元素和的减项
            # 求子区间元素和尾s[i]-s[q[0]],则q[0]与i之间最多相差n，
            # q[0],  i-3,i-2,i-1,i  后面一部分为最长窗口，当n = 4
            if len(q) > 0 and i - n > q[0]: 
                q.popleft()
            if len(q) > 0:
                res = max(res, sum[i] - sum[q[0]])
            # 当队尾大于等于待加入元素，则删除队尾，维护单调上升队列
            while len(q) > 0 and sum[q[-1]] >= sum[i]:
                q.pop()
            q.append(i)
            i += 1
        return res