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:

Complexity

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:

or

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.

So store it first.

int prevNoDelete = noDelete;

Then update.

Complete DP Formula

prev = noDelete

noDelete =
max(arr[i],
    noDelete + arr[i])

oneDelete =
max(prev,
    oneDelete + arr[i])

answer =
max(answer,
    noDelete,
    oneDelete)

Dry Run

Example

arr =
1 2 3 -4 5

Initially:

noDelete = 1
oneDelete = 1
answer = 1

i = 1

Value = 2

prev = 1

noDelete =
max(2,1+2)=3

oneDelete =
max(1,1+2)=3

answer=3

i = 2

Value = 3

prev=3

noDelete=
max(3,3+3)=6

oneDelete=
max(3,3+3)=6

answer=6

i = 3

Value = -4

prev=6

noDelete=
max(-4,6-4)=2

oneDelete=
max(6,6-4)=6

answer=6

Notice:

Deleting -4 gives us 6.

i = 4

Value = 5

prev=2

noDelete=
max(5,2+5)=7

oneDelete=
max(2,6+5)=11

answer=11

Final Answer

11

Correct Java Solution (O(1) Space)

class Solution {
    public int maxSumSubarray(int[] arr) {

        int noDelete = arr[0];
        int oneDelete = arr[0];
        int ans = arr[0];

        for (int i = 1; i < arr.length; i++) {

            int prevNoDelete = noDelete;

            noDelete = Math.max(arr[i], noDelete + arr[i]);

            oneDelete = Math.max(prevNoDelete, oneDelete + arr[i]);

            ans = Math.max(ans, Math.max(noDelete, oneDelete));
        }

        return ans;
    }
}

Why Does This Work?

At every index:

Every possible optimal subarray falls into one of these two categories, so taking the maximum of them at every step guarantees the global optimum.

Complexity Analysis

ComplexityValue
TimeO(N)
SpaceO(1)

Key Takeaways

noDelete = max(arr[i], noDelete + arr[i])

oneDelete = max(previousNoDelete,
                oneDelete + arr[i])

Summary

This problem extends Kadane's Algorithm by maintaining two dynamic programming states: one for the maximum subarray sum without any deletion and another for the maximum subarray sum after deleting at most one element. By updating these states in a single pass through the array, the algorithm efficiently computes the maximum possible subarray sum in O(N) time using O(1) extra space, making it suitable for handling very large input sizes.