Coding Interview: Maximum Subarray Sum with One Deletion

What the interviewer evaluates

Given an integer array, return the maximum sum of a non-empty contiguous subarray after deleting at most one element. The deletion is optional, and the remaining elements must come from one contiguous interval.

Constraints and boundaries

• The array is non-empty and may contain negative, zero, or positive values.
• The result cannot be an empty array.
• Deleting an interval endpoint is equivalent to excluding that endpoint from the chosen interval.
• Aim for one scan rather than enumerating a deletion position and two subarrays.

Turn deletion into a state

Maintain keep, the best sum ending at the current index with no deletion, and drop, the best sum ending there after one deletion. For a value x, keep chooses restarting or extending; drop chooses deleting x or extending an already-deleted state.

Separate result states from intermediate states

The answer must inspect both states because the optimum may use no deletion or remove a negative value. Initializing drop to zero would allow an empty subarray or a deletion of a nonexistent element.

Explain linear complexity

Each value updates two constant-size states, so time is O(n) and extra space is O(1). The states are complete because every valid interval ending here has either made no deletion or exactly one deletion.

Clarifying questions before answering

• Does “at most one” include no deletion? Requiring exactly one changes the answer and the single-element boundary.
• Must the result be non-empty? Allowing empty output can incorrectly make zero the answer.
• Can the sum overflow a 32-bit integer? This determines the accumulator type and test range.

30-second answer framework

“I keep two states ending at the current index: keep has no deletion and drop has one. For x, keep is restart or extend; drop is delete x or extend the old drop. The answer is the maximum seen in both states. I initialize from the first element rather than zero for all-negative inputs, achieving O(n) time and O(1) space.”

Step-by-step deep dive

Let the previous states be keepPrev and dropPrev. Update them as follows:

keep = max(x, keepPrev + x)
drop = max(dropPrev + x, keepPrev)

The second line's keepPrev means deleting the current element; the old interval already contains an element. dropPrev + x means deletion happened earlier and the current value is appended. Save the old values before overwriting either state.

For a one-element array, keep is that element and drop must not represent a legal empty interval. Initialize drop to negative infinity and update from the second element, or define explicit first-element semantics while preserving the non-empty rule.

Model high-quality answer

“I split the problem into two DP states. keep is the best sum ending at this index without deletion; drop is the best sum after one deletion. For each x, using the old states, compute keep=max(x, keep+x) and drop=max(drop+x, oldKeep). I initialize from the first value so an all-negative array never returns zero, then take the maximum over both states. Each value costs constant work, giving O(n) time and O(1) space.”

Common mistakes

• Running ordinary Kadane without a state for deletion.
• Initializing drop to zero and permitting an empty interval.
• Computing drop from the already-updated keep, using one value twice.
• Allowing an empty result without clarifying the problem boundary.
• Testing only positive arrays and missing all-negative, one-element, and endpoint deletion cases.

Failure symptoms and fixes

Returning zero for [-5] violates the non-empty rule. If [1,-2,0,3] never beats ordinary Kadane, the deletion state is not contributing. Write the invariant first, then trace a small array one transition at a time.

Production implementation

Use an accumulator wide enough for the input range. To return the interval, carry start, deletion index, and end metadata with each state; the number of states remains constant, but tie-breaking must be deterministic.

Verification checklist

Test one element, all negative, all positive, deleting a middle negative, deleting an endpoint, multiple optima, and maximum values. For small arrays, compare against an O(n²) reference that enumerates the optional deletion and runs Kadane, using randomized differential tests.

Follow-up questions and answers

What changes if one deletion is mandatory?

You cannot simply return keep, because the solution must use drop. A one-element array has no legal non-empty result, so the API needs an explicit sentinel or a minimum input length.

Can prefix sums solve it?

Prefix sums can enumerate deletion positions and intervals in O(n²). Left and right maximum-subarray preprocessing reaches O(n) with O(n) space; the two-state scan is more space efficient.

How do you recover the actual interval?

Carry a start and deletion index with each state. Reset the start when restarting, record the index when deleting the current value, and backtrack the end from the state that produced the best answer.

Scoring rubric

• State definition: clearly distinguishes no deletion from one deletion.
• Correct transitions: uses old states and covers restart, extension, and deleting current.
• Complete boundaries: handles all-negative, one-element, non-empty, and overflow cases.
• Accurate complexity: reaches O(n) time and O(1) extra space.
• Strong verification: proposes a reference enumerator and boundary-focused tests.

Compliance check

Confirm that state transitions, non-empty boundaries, and complexity claims stay consistent.

Interview answer checklist

State the two invariants, write both transitions, emphasize saving old values and first-element initialization, then give complexity and randomized differential testing.

One-sentence takeaway

Allowing one deletion adds an “already deleted” dimension to Kadane’s contiguous-state DP, yielding a non-empty optimum in linear time and constant space.