区间动态规划例题：最大子数组和问题（允许最多删除一个元素） 题目描述 给定一个整数数组，要求找到一个具有最大和的连续子数组（允许最多删除一个元素，也可以不删除）。返回这个最大和。例如，对于数组 [1, -2, 0, 3] ，删除元素 -2 后，连续子数组 [1, 0, 3] 的和为 4，这是最大和。 解题思路 本题是基础最大子数组和问题的扩展，允许在子数组中最多删除一个元素。我们可以使用动态规划来记录两个状态： dp_no_delete[i] ：以第 i 个元素结尾且没有删除任何元素的最大子数组和。 dp_delete[i] ：以第 i 个元素结尾且已经删除了一个元素的最大子数组和。 通过遍历数组，逐步更新这两个状态，最终取所有状态的最大值作为答案。 步骤详解 状态定义 dp_no_delete[i] ：表示以第 i 个元素结尾且未删除任何元素的最大子数组和。 dp_delete[i] ：表示以第 i 个元素结尾且已经删除了一个元素的最大子数组和（删除的元素可以是第 i 个元素之前的某个元素）。 初始化 对于第一个元素（索引 0）： dp_no_delete[0] = nums[0] （只有一个元素，必须选）。 dp_delete[0] = 0 （如果删除第一个元素，子数组为空，和为 0；但题目允许删除后子数组为空，但空子数组和为 0，通常我们考虑非空子数组，但这里需注意边界）。实际上，更合理的初始化是：在第一个元素处，如果删除它，则没有元素可选，但题目允许空子数组吗？通常我们要求非空子数组，所以应避免空子数组。因此，我们初始化 dp_delete[0] 为负无穷或一个极小值，表示无效状态。但为了简化，我们可以从第二个元素开始考虑删除操作。 状态转移方程 对于 dp_no_delete[i] ： 与经典最大子数组和相同： dp_no_delete[i] = max(nums[i], dp_no_delete[i-1] + nums[i]) 。 对于 dp_delete[i] ： 有两种情况： 情况一：之前已经删除过一个元素，那么当前元素必须加入，即 dp_delete[i] = dp_delete[i-1] + nums[i] 。 情况二：之前没有删除过元素，现在删除当前元素，那么子数组和等于以 i-1 结尾的最大未删除子数组和，即 dp_no_delete[i-1] （因为删除当前元素后，子数组截止到 i-1 ）。 综上： dp_delete[i] = max(dp_delete[i-1] + nums[i], dp_no_delete[i-1]) 。 遍历与结果 从 i=1 开始遍历数组，更新 dp_no_delete[i] 和 dp_delete[i] 。 最终答案是所有 dp_no_delete[i] 和 dp_delete[i] 中的最大值（注意至少选一个元素，所以不能全为负时取 0，除非题目允许空子数组）。 示例演算 数组： [1, -2, 0, 3] i=0: dp_no_delete[0] = 1 dp_delete[0] 无效（设为负无穷），因为第一个元素不能删除后还有子数组。 i=1: dp_no_delete[1] = max(-2, 1 + (-2)) = max(-2, -1) = -1 dp_delete[1] = max(无效状态 + (-2), dp_no_delete[0]) = max(无效, 1) = 1 （删除当前元素 -2） i=2: dp_no_delete[2] = max(0, -1 + 0) = 0 dp_delete[2] = max(1 + 0, dp_no_delete[1]) = max(1, -1) = 1 i=3: dp_no_delete[3] = max(3, 0 + 3) = 3 dp_delete[3] = max(1 + 3, dp_no_delete[2]) = max(4, 0) = 4 最大值 among all: max(1, -1, 1, 0, 3, 4) = 4 。 复杂度分析 时间复杂度：O(n)，只需遍历一次数组。 空间复杂度：O(n)，可以用两个变量优化到 O(1)。 通过以上步骤，我们解决了允许最多删除一个元素的最大子数组和问题。