Maximize Subarray Sum with One Deletion – LeetCode 1186 Solution

LeetCode 1186 – Delete One Element to Maximize Subarray Sum (Medium)

Given an integer array arr, return the maximum possible sum of a non‑empty contiguous subarray after optionally deleting at most one element. The subarray must contain at least one element after deletion.

Example

Input: arr = [1, -2, 0, 3] Output: 4 Explanation: Choose the whole array and delete -2, resulting in [1, 0, 3] whose sum is 4.

Constraints

1 ≤ arr.length ≤ 10⁵

-10⁴ ≤ arr[i] ≤ 10⁴

Problem Analysis

We can solve the problem with dynamic programming. Define dp[i][0] as the maximum sum of a subarray ending at index i without any deletion, and dp[i][1] as the maximum sum of a subarray ending at i with at most one deletion (the deletion may have occurred earlier or be the current element).

Recurrence formulas:

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]);

Base cases: dp[0][0] = arr[0] (no deletion) and dp[0][1] = 0 (delete the first element).

Java Implementation

public int maximumSum(int[] arr) {
    int n = arr.length;
    int[][] dp = new int[n][2];
    dp[0][0] = arr[0]; // first element not deleted
    dp[0][1] = 0;      // first element deleted
    int ans = arr[0];
    for (int i = 1; i < n; 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];
    dp[0][1] = 0;
    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;
}