最大子数组和问题的变种——最多允许删除一个元素的最大子数组和

字数 2299 2025-11-10 07:29:49

最大子数组和问题的变种——最多允许删除一个元素的最大子数组和

题目描述
给定一个整数数组 nums，要求计算其连续子数组的最大和。与经典的最大子数组和问题不同，本题允许在计算过程中最多删除一个元素（也可以不删除），以使得子数组和尽可能大。注意：删除元素后，剩余元素必须保持原始顺序，且子数组必须是连续的。要求设计一个时间复杂度为 O(n) 的算法。

示例：
输入：nums = [1, -2, 0, 3]
输出：4
解释：删除元素 -2 后，子数组 [1, 0, 3] 的和为 4。

解题过程

步骤1：理解问题核心
经典的最大子数组和问题（Kadane算法）通过动态规划记录以每个位置结尾的最大子数组和。本题允许最多删除一个元素，相当于在任意连续子数组中，可以跳过（删除）一个元素，但剩余元素必须连续。我们需要扩展经典动态规划状态来记录这种“允许跳过”的情况。

步骤2：定义动态规划状态
定义两个动态规划数组：

dp_no_delete[i]：表示以 nums[i] 结尾、且未删除任何元素的最大子数组和。
dp_delete[i]：表示以 nums[i] 结尾、且已经删除过一个元素的最大子数组和。

步骤3：状态转移方程

对于 dp_no_delete[i]：
- 如果 dp_no_delete[i-1] 为正，则加上 nums[i] 更优：dp_no_delete[i] = dp_no_delete[i-1] + nums[i]。
- 否则，从 nums[i] 重新开始：dp_no_delete[i] = nums[i]。
- 转移方程：

\[ dp\_no\_delete[i] = \max(nums[i],\ dp\_no\_delete[i-1] + nums[i]) \]

对于 dp_delete[i]：
- 情况1：在之前已经删除过元素，当前元素 nums[i] 必须保留。此时继承 dp_delete[i-1] 并加上 nums[i]：

\[ \text{case1} = dp\_delete[i-1] + nums[i] \]

情况2：在当前元素之前未删除过元素，但当前考虑删除之前某个元素。注意，删除操作只能进行一次，且删除的元素不能是当前元素。实际上，删除一个元素等价于将两个不连续的子段连接起来。具体来说，如果删除 nums[i-1]，则当前子数组由 以 nums[i-2] 结尾的子数组 和 nums[i] 连接而成：

\[ \text{case2} = dp\_no\_delete[i-2] + nums[i] \quad (\text{如果 } i \geq 2) \]

综合两种情况：

\[ dp\_delete[i] = \max(\text{case1},\ \text{case2}) \]

边界处理：当 i < 2 时，case2 不可用，仅考虑 case1。

步骤4：初始化

dp_no_delete[0] = nums[0]
dp_delete[0] 无法在位置0就完成删除（因为删除后无元素），初始化为极小值（如 -inf），但更合理的处理是：在 i=1 时，dp_delete[1] 可直接由删除 nums[0] 得到，即 dp_delete[1] = nums[1]。
我们可以统一处理：
- 设 dp_no_delete[0] = nums[0], dp_delete[0] = -10^9（表示无效状态）。
- 对于 i=1：
  - dp_no_delete[1] = max(nums[1], nums[0] + nums[1])
  - dp_delete[1] = nums[1]（删除 nums[0]）

步骤5：计算全局最大值
最终答案是所有 dp_no_delete[i] 和 dp_delete[i] 中的最大值，因为允许不删除或删除一个元素。

步骤6：示例演算
以 nums = [1, -2, 0, 3] 为例：

i=0:
- dp_no_delete[0] = 1
- dp_delete[0] = -inf
i=1:
- dp_no_delete[1] = max(-2, 1 + (-2)) = max(-2, -1) = -1
- dp_delete[1] = nums[1] = -2（删除nums[0]）
i=2:
- dp_no_delete[2] = max(0, -1 + 0) = max(0, -1) = 0
- dp_delete[2] = max(dp_delete[1] + 0, dp_no_delete[0] + 0) = max(-2 + 0, 1 + 0) = max(-2, 1) = 1
i=3:
- dp_no_delete[3] = max(3, 0 + 3) = 3
- dp_delete[3] = max(dp_delete[2] + 3, dp_no_delete[1] + 3) = max(1 + 3, -1 + 3) = max(4, 2) = 4
  全局最大值：max(1, -inf, -1, -2, 0, 1, 3, 4) = 4。

步骤7：复杂度分析
每个位置的计算是 O(1)，总时间复杂度 O(n)，空间复杂度 O(n)（可优化为 O(1) 仅保留前两个状态）。

通过以上步骤，我们解决了“最多允许删除一个元素的最大子数组和”问题。

最大子数组和问题的变种——最多允许删除一个元素的最大子数组和题目描述给定一个整数数组 nums ，要求计算其连续子数组的最大和。与经典的最大子数组和问题不同，本题允许在计算过程中最多删除一个元素（也可以不删除），以使得子数组和尽可能大。注意：删除元素后，剩余元素必须保持原始顺序，且子数组必须是连续的。要求设计一个时间复杂度为 O(n) 的算法。示例：输入：nums = [ 1, -2, 0, 3 ] 输出：4 解释：删除元素 -2 后，子数组 [ 1, 0, 3 ] 的和为 4。解题过程步骤1：理解问题核心经典的最大子数组和问题（Kadane算法）通过动态规划记录以每个位置结尾的最大子数组和。本题允许最多删除一个元素，相当于在任意连续子数组中，可以跳过（删除）一个元素，但剩余元素必须连续。我们需要扩展经典动态规划状态来记录这种“允许跳过”的情况。步骤2：定义动态规划状态定义两个动态规划数组： dp_no_delete[i] ：表示以 nums[i] 结尾、且未删除任何元素的最大子数组和。 dp_delete[i] ：表示以 nums[i] 结尾、且已经删除过一个元素的最大子数组和。步骤3：状态转移方程对于 dp_no_delete[i] ：如果 dp_no_delete[i-1] 为正，则加上 nums[i] 更优： dp_no_delete[i] = dp_no_delete[i-1] + nums[i] 。否则，从 nums[i] 重新开始： dp_no_delete[i] = nums[i] 。转移方程： \[ dp\_no\_delete[ i] = \max(nums[ i],\ dp\_no\_delete[ i-1] + nums[ i ]) \] 对于 dp_delete[i] ：情况1：在之前已经删除过元素，当前元素 nums[i] 必须保留。此时继承 dp_delete[i-1] 并加上 nums[i] ： \[ \text{case1} = dp\_delete[ i-1] + nums[ i ] \] 情况2：在当前元素之前未删除过元素，但当前考虑删除之前某个元素。注意，删除操作只能进行一次，且删除的元素不能是当前元素。实际上，删除一个元素等价于将两个不连续的子段连接起来。具体来说，如果删除 nums[i-1] ，则当前子数组由以 nums[i-2] 结尾的子数组和 nums[i] 连接而成： \[ \text{case2} = dp\_no\_delete[ i-2] + nums[ i ] \quad (\text{如果 } i \geq 2) \] 综合两种情况： \[ dp\_delete[ i ] = \max(\text{case1},\ \text{case2}) \] 边界处理：当 i < 2 时， case2 不可用，仅考虑 case1。步骤4：初始化 dp_no_delete[0] = nums[0] dp_delete[0] 无法在位置0就完成删除（因为删除后无元素），初始化为极小值（如 -inf ），但更合理的处理是：在 i=1 时， dp_delete[1] 可直接由删除 nums[0] 得到，即 dp_delete[1] = nums[1] 。我们可以统一处理：设 dp_no_delete[0] = nums[0] , dp_delete[0] = -10^9 （表示无效状态）。对于 i=1 ： dp_no_delete[1] = max(nums[1], nums[0] + nums[1]) dp_delete[1] = nums[1] （删除 nums[ 0 ]）步骤5：计算全局最大值最终答案是所有 dp_no_delete[i] 和 dp_delete[i] 中的最大值，因为允许不删除或删除一个元素。步骤6：示例演算以 nums = [ 1, -2, 0, 3 ] 为例： i=0: dp_no_delete[0] = 1 dp_delete[0] = -inf i=1: dp_no_delete[1] = max(-2, 1 + (-2)) = max(-2, -1) = -1 dp_delete[1] = nums[1] = -2 （删除nums[ 0 ]） i=2: dp_no_delete[2] = max(0, -1 + 0) = max(0, -1) = 0 dp_delete[2] = max(dp_delete[1] + 0, dp_no_delete[0] + 0) = max(-2 + 0, 1 + 0) = max(-2, 1) = 1 i=3: dp_no_delete[3] = max(3, 0 + 3) = 3 dp_delete[3] = max(dp_delete[2] + 3, dp_no_delete[1] + 3) = max(1 + 3, -1 + 3) = max(4, 2) = 4 全局最大值：max(1, -inf, -1, -2, 0, 1, 3, 4) = 4。步骤7：复杂度分析每个位置的计算是 O(1)，总时间复杂度 O(n)，空间复杂度 O(n)（可优化为 O(1) 仅保留前两个状态）。通过以上步骤，我们解决了“最多允许删除一个元素的最大子数组和”问题。