思路

• 分析题意：根据yxc讲述
• 对于环形问题：将n的环展开成一条2*n的链
• 每次找答案就在区间为n的部分里面找
• 原题求的是子数组的最大可能和
• 即max[l,r] ->这里我们用前缀和先预处理
• 答案就是 sum[r] - sum[l] (原数组下标从1开始)
• 何时更新答案呢?
• 当新入队元素的前缀和变小的时候更新答案
• 当窗口大小大于n的时候出队

class Solution {
    public int maxSubarraySumCircular(int[] A) {
        int n = A.length;
        int[] tmp = new int[2*n];
        for(int i = 0 ; i < n ; i++)
            tmp[i] = A[i];
        for(int i = n ; i < 2* n ; i++){
            tmp[i] = A[i - n];
        }
        int[] sum = new int[2*n+1];
        for(int i = 1 ; i <= 2*n ;i++)
            sum[i] = sum[i-1] + tmp[i-1];
        int[] q = new int[60010];
        int tt = 0,hh = 0;
        q[0] = 0;
        int ans = Integer.MIN_VALUE;
        for(int i = 1; i <= 2*n ; i++){
            if(hh <=tt && i - q[hh] > n)
                hh++;
            //更新答案
            if(hh <= tt)
                ans = Math.max(ans,sum[i] - sum[q[hh]]);
            while(hh <= tt && sum[q[tt]] >= sum[i])
                tt--;
            q[++tt] = i;
        }
        return ans;   
    }
}