Java 数组最大子数组和：删除一个元素求最大值

本文介绍了如何使用 Java 语言求解一个整数数组在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。

解题思路：

用一个数组 leftMax 存储从左往右遍历时，每个位置结尾的最大子数组和，即子数组必须以该位置为结尾。leftMax[i] 就是以 i 结尾的最大子数组和。
用一个数组 rightMax 存储从右往左遍历时，每个位置开头的最大子数组和，即子数组必须从该位置开始。rightMax[i] 就是以 i 开头的最大子数组和。
最后，遍历一遍数组，对于每个位置 i，计算 leftMax[i-1]+rightMax[i] 的值，即删除 i 位置上的数所能得到的最大子数组和，取所有结果中的最大值即可。

代码实现：

public int maximumSum(int[] arr) {
    int n = arr.length;
    int[] leftMax = new int[n];
    int[] rightMax = new int[n];
    int maxSum = arr[0];
    leftMax[0] = arr[0];
    for (int i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i-1] + arr[i], arr[i]);
        maxSum = Math.max(maxSum, leftMax[i]);
    }
    rightMax[n-1] = arr[n-1];
    for (int i = n-2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i+1] + arr[i], arr[i]);
    }
    for (int i = 1; i < n-1; i++) {
        maxSum = Math.max(maxSum, leftMax[i-1] + rightMax[i]);
    }
    return maxSum;
}

通过上述代码，我们可以轻松地求解出数组在执行一次删除操作后所能得到的最大子数组和。