Java 实现 最大连续子数组和（允许删除一个元素）

Java 实现 最大连续子数组和（允许删除一个元素）

本文将介绍如何使用 Java 语言实现一个算法，该算法能够在一个整数数组中找到一个非空子数组，该子数组在执行一次可选的删除操作后，能够得到最大的元素总和。

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

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

解题思路：

首先，我们可以遍历一遍整个数组，记录下每个位置左边的最大连续子数组和和右边的最大连续子数组和。然后，再遍历一遍数组，对于每个位置，我们计算它左边的最大连续子数组和加上右边的最大连续子数组和（如果这两个数组不相交），或者是左边最大连续子数组和加上右边最大连续子数组和减去中间被删除的那个元素的值（如果这两个数组相交），取最大值即可。

具体实现细节可以看下面的代码：

public int maximumSum(int[] arr) {
    int n = arr.length;
    int[] leftMax = new int[n]; // 左边最大连续子数组和
    int[] rightMax = new int[n]; // 右边最大连续子数组和

    // 计算左边最大连续子数组和
    int curSum = 0;
    for (int i = 0; i < n; i++) {
        curSum = Math.max(curSum + arr[i], arr[i]);
        leftMax[i] = curSum;
    }

    // 计算右边最大连续子数组和
    curSum = 0;
    for (int i = n - 1; i >= 0; i--) {
        curSum = Math.max(curSum + arr[i], arr[i]);
        rightMax[i] = curSum;
    }

    int ans = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        int sum = leftMax[i] + rightMax[i] - arr[i]; // 不删元素的情况
        ans = Math.max(ans, sum);

        if (i > 0) { // 删掉左边的元素
            sum = rightMax[i]; // 右边最大连续子数组和
            if (leftMax[i - 1] > 0) { // 左边最大连续子数组和
                sum += leftMax[i - 1];
            }
            ans = Math.max(ans, sum);
        }

        if (i < n - 1) { // 删掉右边的元素
            sum = leftMax[i]; // 左边最大连续子数组和
            if (rightMax[i + 1] > 0) { // 右边最大连续子数组和
                sum += rightMax[i + 1];
            }
            ans = Math.max(ans, sum);
        }
    }

    return ans;
}