本文主要是介绍【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
这篇关于【LeetCode】918. 环形子数组的最大和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
