918. 环形子数组的最大和

题目描述

数组是环形数组，且含有负数，求一个子数组，具有最大和

基本分析

1. 怎么处理环？破环成链，将n的环展开成2*n的链，在不超过n的窗口内遍历
2. 之后怎么做？在2*n的数组上计算长度不超过n的子数组的最大和，用单调队列就行
3. 为啥弹出的条件是i-q[0] > n , 等于不行？当前遍历到i时，索引是i-1，满足长度n的最小索引是 i -1 - n + 1 = i - n；这个索引前一个索引是i-n-1，对应的前缀和索引是i-n-1+1 = i - n

代码

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        n = len(nums)
        s = [0]
        for _ in range(2):
            for num in nums:
                s.append(s[-1] + num)
        ans = -inf

        q = deque([0])

        for i, cur_s in enumerate(s[1:], 1):
            if q and q[0] < i - n:
                q.popleft()
            ans = max(ans, cur_s - s[q[0]])

            while q and cur_s <= s[q[-1]]:
                q.pop()
            q.append(i)
        
        return ans

总结

1. 对环的处理
2. 为什么能引入单调队列？在双倍长度上维护长度为k的窗口
3. 单调队列的核心是什么？从前端弹出不再满足约束的值；从后端弹出不必要的值。