0918. Maximum Sum Circular Subarray¶
题目信息¶
- 题号:
0918
- 难度:
Medium
- 主题:
数组、环形连续子数组、最大和
- 原题:
- 重点:
所选子数组必须非空且在环形顺序中连续,可以跨越末尾与开头;任何下标最多使用一次
题目重述¶
给定整数数组 nums,把它视为首尾相连的环形数组。选择一个非空的连续区间:区间可以完全位于普通数组内部,也可以从数组末尾跨越到开头。
同一个数组下标不能在所选区间中出现两次,因此不能绕环超过一周。请返回所有合法非空环形子数组中的最大元素和。
1 <= nums.length <= 3 * 10^4,-3 * 10^4 <= nums[i] <= 3 * 10^4。
自建示例¶
最优区间跨越数组边界:
输入:nums = [5,-2,3]
输出:8
解释:选择末尾的 3 和开头的 5,形成环形连续子数组 [3,5],和为 8。每个下标只使用一次。
所有元素均为负数:
输入:nums = [-4,-2,-7]
输出:-2
解释:子数组必须非空,选择单个元素 -2 比包含任何其他负数的连续区间更优,因此最大和为 -2。