0918. Maximum Sum Circular Subarray

题目信息

题号:

0918

难度:

Medium

主题:

数组、环形连续子数组、最大和

原题:

LeetCode 0918

重点:

所选子数组必须非空且在环形顺序中连续,可以跨越末尾与开头;任何下标最多使用一次

题目重述

给定整数数组 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。