918. 环形子数组的最大和

这道题我们用双端队列解决。首先将数组扩展为两倍，用i%n即可成立，然后使用前缀和去求解最大的字串和。

prei是固定的所以每次找到最小的prej即可，再将每次最大的值放到res中即可。并且要维护这个队列使其递增，这样每次取头部元素即可，因为长度不超过n，所以i-j小于n的就出队，并且前缀和大于当前前缀和的从尾部出队，这要可以保证递增性，也能保证不丢失可能存在的解。

class Solution { public: int maxSubarraySumCircular(vector<int>& nums) { int n=nums.size(); int pre=nums[0],res=nums[0]; deque<pair<int,int>> q; q.push_back({0,pre}); for(int i=1;i<2*n;i++){ while(!q.empty()&&q.front().first<i-n){ q.pop_front(); } pre+=nums[i%n]; res=max(res,pre-q.front().second); while(!q.empty()&&q.back().second>=pre){ q.pop_back(); } q.push_back({i,pre}); } return res; } };