题目

---

1186. 删除一次得到子数组最大和

给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。

注意，删除一个元素后，子数组 不能为空。

示例 1：

输入：arr = [1,-2,0,3]
输出：4
解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。

示例 2：

输入：arr = [1,-2,-2,3]
输出：3
解释：我们直接选出 [3]，这就是最大和。

示例 3：

输入：arr = [-1,-1,-1,-1]
输出：-1
解释：最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。
     我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。

class Solution {
    public int maximumSum(int[] arr) {

    }
}

分析

---

本题目出自2023.6.27每日练习

第一次分析动态规划的题比较难,没有什么头绪,所以就看了官方的题解, 一直没有好好的理解动态规划的规律,这个题就是尤其是有两个转移方程的情况.

这个问题解决方案的核心是 当前 i元素 子数组的最大值 = (i-1元素 子数组的最大值) +?? (当前 i元素 的值)

+?? 表示是否要新增

所以像这种情况,我们需要拆分成两部分来分析.

• 当前i元素的子数组不删除任意一个元素.

  如果 i = 0; 那结果就是 dp[0] = arr[0];

  如果 i = 1; 那就需要分析前一个元素子数组情况 dp[0] 是否小于0, 小于0的话,我们就直接抛弃 dp[0], dp[1] = arr[1]; 如果大于0,那肯定不能舍弃, 所以结果就为 dp[1] = dp[0] + arr[1].

  如果 i = 2; 和 i = 1 的分析是一致的.

  这样,我们就能得到 当 i = arr.length - 1 时,到底是哪一个片段的值是最大的.

• 当前i元素的子数组删除一个元素.

  还是如上分析

  如果 i = 0; 由于需要删除一个元素,也就是不添加第一个元素, 所以转移方程就变成了 dp[0] = 0;

  如果 i = 1; 那么情况分为两种情况;

  • 一个是删除当前 i = 1 的元素. 也就说结果是 当前i - 1 元素的子数组不删除任意一个元素 ,和上面那种不删除元素的转移方程式一致的,这里需要上面的转移方程的协助. 所以结果就是 dp[1] = dp(不删除元素的转移方程)[0]

  • 另外一个就是在 i = (1 - 1) 就已经删除一个元素,我们只需要把当前元素添加到转移方程上即可,也就是 dp[1] = dp[0] + arr[1]

  • 比较这两种情况的大小值,取较大值.

  如果 i = 2; 那么情况分为两种情况,与 i = 1 类似.

  以此类推,我们可以得到 当 i = arr.length - 1, 在删除一个元素的情况下,能获取到的最大值.

然后在 i 阶段要比较 删除 和 不删除两种的情况,取最大值. 最后取到 i = arr.length - 1 时就是本题的解题结果.

由于是最大值的缘故,我们不需要保存转移方程数组,我们只需要定义 dp0 为不删除任意一个元素时的最大值. dp1 为删除某个元素的最大值,然后result 为最大值的最终结果.故代码如下所示.

int dp0 = arr[0];
int dp1 = 0; // 不添加i = 0 的元素
int result = arr[0]; // 根据后一步会筛选掉 arr[0] 是否是最大值

然后 通过对数组的一次遍历,来给各个数据进行赋值和判断.如下所示

for (int i = 1; i < arr.length; i++) {
    // dp0 这里就表示 i - 1 不删除,但是删除了 arr[i] 的情况
    // dp1 + arr[i] 表示 在前面删除了一个元素, 不删除 arr[i] 的情况
    dp1 = Math.max(dp0, dp1 + arr[i]);
    //  Math.max(dp0, 0) 表示判断 i - 1 的转移方程的值是否大于0,小于0的话就直接抛弃
    // + arr[i] 就是正常流程,把当前的元素添加到递归方程上.
    dp0 = Math.max(dp0, 0) + arr[i];
    // 结果需要 result dp1 dp0 三者进行比较.
    result = Math.max(result, Math.max(dp1, dp0));
}

所以整体代码如下所示.

class Solution {
    public int maximumSum(int[] arr) {
        int dp0 = arr[0];
        int dp1 = 0; // 不添加i = 0 的元素
        int result = arr[0]; // 根据后一步会筛选掉 arr[0] 是否是最大值
        for (int i = 1; i < arr.length; i++) {
            // dp0 这里就表示 i - 1 不删除,但是删除了 arr[i] 的情况
            // dp1 + arr[i] 表示 在前面删除了一个元素, 不删除 arr[i] 的情况
            dp1 = Math.max(dp0, dp1 + arr[i]);
            //  Math.max(dp0, 0) 表示判断 i - 1 的转移方程的值是否大于0,小于0的话就直接抛弃
            // + arr[i] 就是正常流程,把当前的元素添加到递归方程上.
            dp0 = Math.max(dp0, 0) + arr[i];
            // 结果需要 result dp1 dp0 三者进行比较.
            result = Math.max(result, Math.max(dp1, dp0));
        }
        return result;
    }
}