Maximum Subarray Sum After Deleting One Element (LeetCode 1186) – Problem Analysis and Solution

This article presents LeetCode problem 1186 “Maximum Subarray Sum After One Deletion”, which asks for the largest possible sum of a non‑empty subarray after optionally removing at most one element.

Formally, given an integer array arr, you may choose any contiguous subarray and optionally delete a single element from it; the remaining subarray must contain at least one element, and you must maximize the sum of its elements.

Example: Input arr = [1, -2, 0, 3] yields output 4 because deleting -2 leaves the subarray [1, 0, 3] with sum 4. The same example is repeated in the article.

Constraints: 1 ≤ arr.length ≤ 10^5 and -10^4 ≤ arr[i] ≤ 10^4.

The solution uses dynamic programming with two states: dp[i][0] denotes the maximum subarray sum ending at index i without any deletion, and dp[i][1] denotes the maximum sum ending at i with at most one deletion. The recurrences are:

dp[i][0] = max(dp[i‑1][0], 0) + arr[i];

dp[i][1] = max(dp[i‑1][1] + arr[i], dp[i‑1][0]);

Base cases are dp[0][0] = arr[0] and dp[0][1] = 0. The answer is the maximum value among all dp[i][0] and dp[i][1].

Java implementation:

public int maximumSum(int[] arr) {
    int n = arr.length;
    int[][] dp = new int[n][2];
    dp[0][0] = arr[0]; // first element without deletion
    dp[0][1] = 0; // first element deleted
    int ans = arr[0];
    for (int i = 1; i < arr.length; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], 0) + arr[i];
        dp[i][1] = Math.max(dp[i - 1][1] + arr[i], dp[i - 1][0]);
        ans = Math.max(ans, Math.max(dp[i][0], dp[i][1]));
    }
    return ans;
}

C++ implementation:

int maximumSum(vector<int> &arr) {
    int n = arr.size();
    vector<vector<int>> dp(n, vector<int>(2, 0));
    dp[0][0] = arr[0]; // first element without deletion
    dp[0][1] = 0; // first element deleted
    int ans = arr[0];
    for (int i = 1; i < n; i++) {
        dp[i][0] = max(dp[i - 1][0], 0) + arr[i];
        dp[i][1] = max(dp[i - 1][1] + arr[i], dp[i - 1][0]);
        ans = max(ans, max(dp[i][0], dp[i][1]));
    }
    return ans;
}

The author, Wang Yibo, is an experienced algorithm enthusiast who has solved over 2000 problems on various platforms and shares detailed solutions and insights through his public account.