环形数组中的最大连续子数组和（允许最多删除一个元素）

题目描述
给定一个环形整数数组 nums，数组长度为 n。你可以执行最多一次操作：删除数组中的任意一个元素。你需要计算在最多删除一个元素的情况下，环形数组中的最大连续子数组和。注意，环形数组意味着子数组可以是连续的，也可以跨越数组的结尾和开头。

示例
输入：nums = [1, -2, 3, -2]
输出：4
解释：如果不删除任何元素，环形数组的最大连续子数组和是 3（子数组 [3]）。如果删除 -2，数组变为 [1, 3]，环形最大连续子数组和是 4（子数组 [3, 1]，因为环形连接）。

解题步骤

步骤1：理解问题关键点

1. 数组是环形的，即子数组可以跨越 nums[n-1] 和 nums[0]。
2. 允许最多删除一个元素（也可以不删除）。
3. 目标：最大化连续子数组的和。

步骤2：分解问题情况
最大和可能来自以下情况：

• 情况1：不删除任何元素，求环形数组的最大连续子数组和。
• 情况2：删除一个元素，相当于求非环形数组中删除一个元素后的最大连续子数组和（因为删除后数组变成线性）。

步骤3：解决情况1（环形数组最大子数组和）
环形数组的最大子数组和 = max(最大子数组和, 数组总和 - 最小子数组和)

• 如果最小子数组和等于数组总和（全负数），则最大子数组和就是数组中的最大值。
• 实现时，用 Kadane 算法分别求最大子数组和 maxSum 和最小子数组和 minSum，然后比较 maxSum 和 sum - minSum。

步骤4：解决情况2（线性数组中删除一个元素的最大子数组和）
用动态规划：

• 定义 leftMax[i] 表示以 i 结尾的最大子数组和。
• 定义 rightMax[i] 表示以 i 开头的最大子数组和。
• 删除第 i 个元素后，最大和可能是 leftMax[i-1] + rightMax[i+1]（即左右两段连接）。
• 遍历所有可能的删除位置 i，取最大值。

步骤5：合并两种情况
最终结果是 max(情况1结果, 情况2结果)。

步骤6：处理边界条件

• 数组长度 n=1 时，删除后和为 0（空子数组），但题目允许空子数组吗？通常空子数组和为 0，但若要求非空，则需特殊处理。这里假设允许空子数组。

步骤7：算法实现伪代码

function maxSubarraySumCircular(nums):
    n = nums.length
    if n == 0: return 0
    if n == 1: return max(0, nums[0])  // 允许空子数组则返回max(0, nums[0])
    
    // 情况1：环形数组最大和（不删除）
    totalSum = sum(nums)
    maxNoDelete = kadaneMax(nums)  // 普通最大子数组和
    minSum = kadaneMin(nums)       // 最小子数组和
    circularMax = max(maxNoDelete, totalSum - minSum) if minSum != totalSum else maxNoDelete
    
    // 情况2：删除一个元素的最大和（线性数组）
    leftMax = array of size n
    rightMax = array of size n
    // 计算leftMax：从左到右的Kadane
    leftMax[0] = nums[0]
    for i from 1 to n-1:
        leftMax[i] = max(nums[i], leftMax[i-1] + nums[i])
    // 计算rightMax：从右到左的Kadane
    rightMax[n-1] = nums[n-1]
    for i from n-2 down to 0:
        rightMax[i] = max(nums[i], rightMax[i+1] + nums[i])
    
    // 遍历删除位置i
    maxDelete = -inf
    for i from 0 to n-1:
        left = leftMax[i-1] if i-1 >= 0 else 0
        right = rightMax[i+1] if i+1 < n else 0
        maxDelete = max(maxDelete, left + right)
    
    // 最终结果
    return max(circularMax, maxDelete)

步骤8：复杂度分析

• 时间复杂度：O(n)，遍历数组常数次。
• 空间复杂度：O(n)，存储 leftMax 和 rightMax 数组。

通过以上步骤，你可以逐步实现并验证这个问题的解法。