class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        //破环成链
        int n=nums.size();
        // 前缀和
        vector<int> s(n*2+1);
        for(int i=1;i<2*n+1;i++)s[i]=s[i-1]+nums[(i-1)%n];
        // 滑动窗口算法
        deque<int> q;
        q.push_back(0);
        int res=INT_MIN;
        for(int i=1;i<2*n+1;i++)
        {
            while(q.size()&&i-q.front()>n)q.pop_front();
            res=max(res, s[i]-s[q.front()]);
            while(q.size()&&s[q.back()]>=s[i])q.pop_back();
            q.push_back(i);
        }
        return res;
    }
};