1186. Maximum Subarray Sum with One Deletion

class Solution {
    public int maximumSum(int[] arr) {
        int n = arr.length;

        // 定义 dp[i][j] 为以 arr[i] 结尾的子数组执行了 j 次删除后所能得到的最大元素总和
        int[][] dp = new int[n][2];
        dp[0][0] = arr[0];
        dp[0][1] = 0;

        int maxSum = arr[0]; // 注意题目要求子数组不能为空，所以此处未使用 dp[0][1]

        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], 0) + arr[i]; // 不执行删除，即必须选择 arr[i], 同时之前也不能执行删除，如果之前的数组之和不能带来贡献，则不使用之前的数组
            dp[i][1] = Math.max(dp[i - 1][1] + arr[i], dp[i - 1][0]); // 共执行一次删除，如果之前执行了删除，那么这次不能执行删除，如果之前没执行删除，那么这次可以不选择 arr[i]

            maxSum = Math.max(maxSum, Math.max(dp[i][0], dp[i][1]));
        }

        return maxSum;
    }
}

References

1186. Maximum Subarray Sum with One Deletion