Problem Statement
Given an integer array arr[], find the maximum sum of a non-empty subarray. You are allowed to remove (skip) at most one element from that subarray.
Note: Even after removing one element, the remaining subarray must not be empty.
Example 1
Input
arr = [1, 2, 3, -4, 5]
Output
11
Explanation
Without deletion:
1 + 2 + 3 + (-4) + 5 = 7
Delete -4:
1 + 2 + 3 + 5 = 11
Maximum sum = 11
Example 2
Input
arr = [-2, -3, 4, -1, -2, 1, 5, -3]
Output
9
Explanation
Delete -2 (at index 4):
4 + (-1) + 1 + 5 = 9
Brute Force Approach
Generate every possible subarray.
For each subarray:
Calculate the sum without deletion.
Try deleting every element once.
Keep the maximum answer.
Complexity
Time:
O(N³)Space:
O(1)
This is far too slow for N = 10⁶.
Observation
This problem is an extension of Kadane's Algorithm.
Normally, Kadane keeps only one state:
Maximum subarray ending at the current index.
Now we have one additional option:
We may delete one element.
So we maintain two DP states.
DP State Definition
State 1: noDelete
Maximum subarray sum ending at the current index without deleting any element.
This is exactly the same as Kadane's Algorithm.
State 2: oneDelete
Maximum subarray sum ending at the current index after deleting at most one element.
This is the new DP state.
Transition for noDelete
This follows Kadane's Algorithm.
Either:
Extend the previous subarray.
or
Start a new subarray.
Formula:
noDelete =
max(
arr[i],
noDelete + arr[i]
)
Transition for oneDelete
Now there are two possibilities.
Case 1
We already deleted one element earlier.
Then simply add the current element.
oneDelete + arr[i]
Example:
4 -1 5
delete happened before
continue adding 5
Case 2
Delete the current element itself.
If the current element is removed, the best sum becomes:
previous noDelete
because the current element contributes nothing.
Example:
1 2 3 -10
Delete -10
Sum = previous noDelete = 6
Therefore:
oneDelete =
max(
previousNoDelete,
oneDelete + arr[i]
)
Why Store previousNoDelete?
Notice this update order:
noDelete = ...
oneDelete = ...
When calculating oneDelete, we need the old value of noDelete.

Join the conversation! Your thoughts help the community grow.