# Maximum Subarray Sum with One Deletion
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion)
Canonical: https://scaleengineer.com/dsa/problems/maximum-subarray-sum-with-one-deletion
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Two Sigma](https://scaleengineer.com/companies/two-sigma)
---
## Problem
Given an array of integers, return the maximum sum for a **non-empty** subarray (contiguous elements) with at most one element deletion. In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.

Note that the subarray needs to be **non-empty** after deleting one element.

**Example 1:**

**Input:** arr = [1,-2,0,3]
**Output:** 4
**Explanation:** Because we can choose [1, -2, 0, 3] and drop -2, thus the subarray [1, 0, 3] becomes the maximum value.

**Example 2:**

**Input:** arr = [1,-2,-2,3]
**Output:** 3
**Explanation:** We just choose [3] and it's the maximum sum.

**Example 3:**

**Input:** arr = [-1,-1,-1,-1]
**Output:** -1
**Explanation:** The final subarray needs to be non-empty. You can't choose [-1] and delete -1 from it, then get an empty subarray to make the sum equals to 0.

**Constraints:**

* `1 <= arr.length <= 105`
* `-104 <= arr[i] <= 104`

# Approaches
## Improved Brute Force
A brute-force approach involves examining every possible contiguous subarray, and for each subarray, calculating the maximum possible sum by either keeping all its elements or deleting one of them. To make this slightly more efficient, instead of a naive O(N^3) approach, we can use nested loops to define the start and end of a subarray. While iterating to expand the subarray, we can simultaneously calculate its sum and track its minimum element. This allows us to find the sum with and without a deletion in O(1) time for each expansion step, leading to an overall O(N^2) complexity.
**Time:** O(N^2), where N is the length of the array. The nested loops iterate through all possible subarrays, which are O(N^2) in number. · **Space:** O(1), as we only use a few variables to keep track of the current state regardless of the input size.
**Pros:** The logic is straightforward and easy to implement.; It uses constant extra space.
**Cons:** The `O(N^2)` time complexity makes it too slow for large input sizes as specified in the constraints, leading to a 'Time Limit Exceeded' error on most platforms.
### Explanation
This approach iterates through all possible start and end points of a subarray. For each subarray `arr[i...j]`, it calculates two potential maximums: the sum of the subarray as is (no deletion), and the sum of the subarray after removing its smallest element (one deletion). The check `j > i` ensures that we only consider deletion for subarrays with at least two elements, so they remain non-empty after deletion. The global maximum across all subarrays and both cases (deletion/no deletion) is the answer.

```java
class Solution {
    public int maximumSum(int[] arr) {
        int n = arr.length;
        if (n == 1) {
            return arr[0];
        }
        int maxSum = arr[0];

        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            int minVal = Integer.MAX_VALUE;
            for (int j = i; j < n; j++) {
                currentSum += arr[j];
                minVal = Math.min(minVal, arr[j]);

                // Case 1: No deletion
                maxSum = Math.max(maxSum, currentSum);

                // Case 2: One deletion
                // We can only delete if the subarray has more than one element
                if (j > i) {
                    maxSum = Math.max(maxSum, currentSum - minVal);
                }
            }
        }
        return maxSum;
    }
}
```
### Algorithm
1. Initialize `max_sum` to the first element of the array, as the subarray must be non-empty.
2. Iterate through the array with an outer loop using index `i` from `0` to `n-1`. This index `i` will represent the starting point of a potential subarray.
3. Inside the outer loop, start an inner loop with index `j` from `i` to `n-1`. This index `j` will be the ending point of the subarray.
4. For each subarray `arr[i...j]`, we maintain its `current_sum` and the `min_val` within it.
5. As the inner loop for `j` progresses, update `current_sum` by adding `arr[j]` and `min_val` by taking `min(min_val, arr[j])`.
6. For each subarray `arr[i...j]`, there are two possibilities for the sum:
    a. **No Deletion**: The sum is simply `current_sum`. We update our global `max_sum` with this value: `max_sum = max(max_sum, current_sum)`.
    b. **One Deletion**: We can delete one element. To maximize the sum, we should delete the smallest element, `min_val`. This is only possible if the subarray has more than one element (i.e., `j > i`). The sum would be `current_sum - min_val`. We update our global `max_sum` with this value as well: `max_sum = max(max_sum, current_sum - min_val)`.
7. After both loops complete, `max_sum` will hold the maximum possible subarray sum with at most one deletion.

## Dynamic Programming with Two Passes
A more efficient approach uses dynamic programming. The core idea is that for any element `arr[i]` we consider deleting, the maximum sum is the sum of the best possible subarray ending just before it (`arr[i-1]`) and the best possible subarray starting just after it (`arr[i+1]`).

We can precompute these values. We use a `forward` pass (left to right) to calculate the maximum subarray sum ending at each index `i`. Then, we use a `backward` pass (right to left) to calculate the maximum subarray sum starting at each index `i`. Finally, we iterate through the array to combine these results and find the overall maximum.
**Time:** O(N), as we perform three separate passes over the array, each taking linear time. O(N) + O(N) + O(N) = O(N). · **Space:** O(N), where N is the length of the array. We use two additional arrays, `forward` and `backward`, each of size N.
**Pros:** Achieves optimal linear time complexity.; The logic is a clear extension of the standard Kadane's algorithm.
**Cons:** Requires O(N) extra space for the two arrays, which can be significant for very large inputs.
### Explanation
This method involves three main passes through the array.

First Pass (Forward): We apply Kadane's algorithm from left to right. We build a `forward` array where `forward[i]` holds the maximum sum of a contiguous subarray ending at index `i`. We also find the maximum value in this `forward` array, which represents the maximum subarray sum without any deletions.

Second Pass (Backward): We apply Kadane's algorithm from right to left. We build a `backward` array where `backward[i]` holds the maximum sum of a contiguous subarray starting at index `i`.

Third Pass (Combine): We iterate through the array from index 1 to `n-2`. For each index `i`, we calculate `forward[i-1] + backward[i+1]`. This value represents the maximum sum we can get if we choose a subarray that spans across `i` and delete `arr[i]`. We compare this with the maximum sum found so far (which was initialized with the no-deletion max sum) and update it if necessary.

```java
class Solution {
    public int maximumSum(int[] arr) {
        int n = arr.length;
        if (n == 1) {
            return arr[0];
        }

        int[] forward = new int[n];
        int[] backward = new int[n];

        // Forward pass (Kadane's from left)
        int currentMax = arr[0];
        forward[0] = arr[0];
        int maxSumNoDeletion = arr[0];
        for (int i = 1; i < n; i++) {
            currentMax = Math.max(arr[i], currentMax + arr[i]);
            forward[i] = currentMax;
            maxSumNoDeletion = Math.max(maxSumNoDeletion, forward[i]);
        }

        // Backward pass (Kadane's from right)
        currentMax = arr[n - 1];
        backward[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            currentMax = Math.max(arr[i], currentMax + arr[i]);
            backward[i] = currentMax;
        }

        // Combine results
        int maxSumWithDeletion = Integer.MIN_VALUE;
        for (int i = 1; i < n - 1; i++) {
            maxSumWithDeletion = Math.max(maxSumWithDeletion, forward[i - 1] + backward[i + 1]);
        }

        return Math.max(maxSumNoDeletion, maxSumWithDeletion);
    }
}
```
### Algorithm
1. The problem can be split into two subproblems: finding the maximum subarray sum with no deletions, and finding the maximum subarray sum with one deletion.
2. **No Deletion Case**: This is the classic maximum subarray problem, which can be solved with Kadane's algorithm. We can compute this while calculating our `forward` array.
3. **One Deletion Case**: If we delete the element `arr[i]`, the resulting subarray is formed by a subarray to the left of `i` and a subarray to the right of `i`. To maximize the sum, we should take the maximum subarray sum ending at `i-1` and add it to the maximum subarray sum starting at `i+1`.
4. **Algorithm Steps**:
    a. Create an array `forward` of size `n`. `forward[i]` will store the maximum subarray sum ending at index `i`. Populate it by iterating from left to right.
    b. While filling `forward`, keep track of the overall maximum sum found so far. This will be our `max_sum_no_deletion`.
    c. Create an array `backward` of size `n`. `backward[i]` will store the maximum subarray sum starting at index `i`. Populate it by iterating from right to left.
    d. Initialize `result = max_sum_no_deletion`.
    e. Iterate from `i = 1` to `n-2`. For each `i`, consider deleting `arr[i]`. The sum would be `forward[i-1] + backward[i+1]`. Update `result = max(result, forward[i-1] + backward[i+1])`.
    f. Return `result`.

## Optimized Single-Pass Dynamic Programming
The most optimal solution builds upon the dynamic programming concept but reduces the space complexity to O(1). We can achieve this by realizing that to calculate the state for the current index `i`, we only need the state from the immediate previous index `i-1`. This allows us to use a few variables to keep track of the necessary information instead of entire arrays.

We iterate through the array once, maintaining two key values:
- `no_del`: The maximum subarray sum ending at the current position with zero deletions.
- `one_del`: The maximum subarray sum considering elements up to the current position with one deletion.

The final answer is the maximum value encountered among these two states throughout the iteration.
**Time:** O(N), as we iterate through the input array just once. · **Space:** O(1), as we only use a fixed number of variables to store the DP states.
**Pros:** Achieves optimal O(N) time complexity.; Achieves optimal O(1) space complexity.; Requires only a single pass through the array.
**Cons:** The logic for the state transitions, especially for the `one_del` variable, can be less intuitive to grasp compared to the two-pass approach.
### Explanation
This approach uses a single pass and constant extra space. We define two DP states that we update at each step `i`:

- `no_del`: This tracks the maximum sum of a subarray ending at `i` without any deletions. Its transition is `no_del = max(arr[i], no_del + arr[i])`, which is the standard Kadane's recurrence.
- `one_del`: This tracks the maximum sum of a subarray with one deletion, considering all elements up to `i`. Its transition is `one_del = max(one_del + arr[i], no_del_previous)`. This means we either extend a previously formed one-deletion subarray, or we form a new one-deletion subarray by taking a no-deletion subarray ending at `i-1` and 'deleting' `arr[i]`.

We must be careful to use the `no_del` value from the previous step (`i-1`) when updating `one_del` for the current step `i`. We keep a running `max_sum` of all `no_del` and `one_del` values computed.

```java
class Solution {
    public int maximumSum(int[] arr) {
        int n = arr.length;
        if (n == 1) {
            return arr[0];
        }

        // max subarray sum ending at current index with 0 deletions
        int no_del = arr[0];
        // max subarray sum ending at current index with 1 deletion
        int one_del = arr[0];
        // global max sum
        int maxSum = arr[0];

        for (int i = 1; i < n; i++) {
            // To calculate one_del for index i, we need no_del from index i-1.
            // So we calculate the new one_del before updating no_del.
            // one_del can be: 
            // 1. extending previous one_del subarray: one_del + arr[i]
            // 2. deleting arr[i] from a no_del subarray: no_del (from previous step)
            one_del = Math.max(one_del + arr[i], no_del);

            // Standard Kadane's for no_del
            no_del = Math.max(no_del + arr[i], arr[i]);

            maxSum = Math.max(maxSum, Math.max(one_del, no_del));
        }

        return maxSum;
    }
}
```
### Algorithm
1. Initialize three variables: `max_sum` (the global answer), `no_del` (max subarray sum ending at current index with no deletion), and `one_del` (max subarray sum with one deletion considering elements up to current index). Initialize all to `arr[0]`.
2. Iterate through the array from the second element (`i = 1` to `n-1`).
3. In each iteration, we need to update `one_del` and `no_del`. The order is important.
4. First, update `one_del`. A subarray with one deletion up to index `i` can be formed in two ways:
    a. Take a subarray with one deletion that was formed up to index `i-1`, and extend it with `arr[i]`. The sum is `one_del_previous + arr[i]`.
    b. Take a subarray with no deletions ending at `i-1`, and delete the current element `arr[i]`. The sum is simply `no_del_previous`.
    So, the new `one_del` is `max(one_del + arr[i], no_del)`.
5. Next, update `no_del`. This is the standard Kadane's algorithm update:
    a. Extend the previous `no_del` subarray with `arr[i]`: `no_del + arr[i]`.
    b. Start a new subarray with just `arr[i]`.
    So, the new `no_del` is `max(no_del + arr[i], arr[i])`.
6. After updating both `one_del` and `no_del`, update the global `max_sum` by taking the maximum of `max_sum`, the new `one_del`, and the new `no_del`.
7. After the loop, `max_sum` holds the final answer.

# Solutions
### Java

```java
class Solution {
public
  int maximumSum(int[] arr) {
    int n = arr.length;
    int[] left = new int[n];
    int[] right = new int[n];
    int ans = -(1 << 30);
    for (int i = 0, s = 0; i < n; ++i) {
      s = Math.max(s, 0) + arr[i];
      left[i] = s;
      ans = Math.max(ans, left[i]);
    }
    for (int i = n - 1, s = 0; i >= 0; --i) {
      s = Math.max(s, 0) + arr[i];
      right[i] = s;
    }
    for (int i = 1; i < n - 1; ++i) {
      ans = Math.max(ans, left[i - 1] + right[i + 1]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumSum(vector<int> &arr) {
    int n = arr.size();
    int left[n];
    int right[n];
    for (int i = 0, s = 0; i < n; ++i) {
      s = max(s, 0) + arr[i];
      left[i] = s;
    }
    for (int i = n - 1, s = 0; ~i; --i) {
      s = max(s, 0) + arr[i];
      right[i] = s;
    }
    int ans = *max_element(left, left + n);
    for (int i = 1; i < n - 1; ++i) {
      ans = max(ans, left[i - 1] + right[i + 1]);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumSum(self, arr: List[int]) -> int: n = len(arr) left = [0] * n right = [0] * n s = 0 for i, x in enumerate(arr): s = max(s, 0) + x left[i] = s s = 0 for i in range(n - 1, - 1, - 1): s = max(s, 0) + arr[i] right[i] = s ans = max(left) for i in range(1, n - 1): ans = max(ans, left[i - 1] + right[i + 1]) return ans

```