算法题讲解 - 文章介绍了一道来自LeetCode第1186题的算法题，题目为“删除一次得到子数组最大和”，难度为中等 [5] - 题目要求是给定一个整数数组，返回其某个非空连续子数组在执行最多一次删除操作后所能获得的最大元素总和 [5] - 问题分析指出数组长度约束为 1 <= arr.length <= 10^5，数组元素值约束为 -10^4 <= arr[i] <= 10^4 [8] 解题思路与示例 - 通过两个示例说明题目解法：对于输入 arr = [1,-2,0,3]，最优解是选择子数组 [1, -2, 0, 3] 并删除元素 -2，得到最大和 4 [6][7] - 文章指出该问题本质上是动态规划问题，并定义了两种状态 [9] - 定义 dp[i][0] 表示没有删除任何元素且以 arr[i] 结尾的最大连续子数组之和 [9] - 定义 dp[i][1] 表示最多删除一个元素且以 arr[i] 结尾的最大连续子数组之和 [9] 动态规划递推公式 - 推导出状态转移方程：dp[i][0] = Math.max(dp[i - 1][0], 0) + arr[i] [9] - 推导出状态转移方程：dp[i][1] = Math.max(dp[i - 1][1] + arr[i], dp[i - 1][0]) [9] - 对公式进行解释：dp[i][0] 表示不删除元素，总和为当前元素加上前序子数组和（若为负则舍弃） [9] - 对公式进行解释：dp[i][1] 表示最多删除一次，可能继承已删除状态并加上当前元素，也可能删除当前元素而取前序未删除状态 [9] 初始化与代码实现 - 明确了动态规划的初始条件：第一个元素未删除时 dp[0][0] = arr[0]，第一个元素被删除时 dp[0][1] = 0 [10] - 提供了该算法的Java语言实现代码，包括初始化、循环递推和结果保存 [11] - 提供了该算法的C++语言实现代码，逻辑与Java版本一致 [12]