【LeetCode】918. 环形子数组的最大和

1. 题目

2. 分析

单调队列的经典应用。

3. 代码

class Solution:def maxSubarraySumCircular(self, nums: List[int]) -> int:# 使用单调队列的解法# 转换为求区间长度不超过len(nums)内的最大和k = len(nums)nums = nums + nums# 求出前缀和prefixSum = [0] * len(nums) prefixSum[0] = nums[0]for i in range(1, len(nums)):prefixSum[i] = prefixSum[i-1] + nums[i]# 单调队列求出区间最大和que = [0] * (len(nums) + 1)# 关键点1：left 和 right的初始值为1left = 1right = 1res = nums[0]que[1]= 0 # 将nums的第一个元素放进去for i in range(1, len(nums)): # 遍历区间的每一个数# 更新队列while(left <= right and que[left] < i - k ):left += 1# 更新结果res = max(res, prefixSum[i] - prefixSum[que[left]])# 更新队列while( left <= right and prefixSum[que[right]] >= prefixSum[i]):right -= 1right += 1que[right] = iprint(res)return res