Maximum Subarray Sum with One Deletion

Maximum Subarray Sum with One Deletion

1. What is this problem about?

Maximum Subarray Sum with One Deletion is a strategic optimization problem. You are given an array of integers and you want to find the maximum sum of a non-empty contiguous subarray. However, you are given a special "one-time" power: you can delete at most one element from your chosen subarray to make its sum larger. For example, in the array [1, -2, 0, 3], the maximum subarray sum without deletion is 3. But if you pick [1, -2, 0, 3] and delete -2, the sum becomes 4.

2. Why is this asked in interviews?

This "Maximum Subarray Sum with One Deletion interview question" is a staple at Microsoft, Meta, and Amazon. It tests if a candidate can handle complex Dynamic Programming transitions. It specifically evaluates whether you can track two parallel possibilities: the best sum without any deletions and the best sum where one deletion has already occurred. It's a great test of logical consistency and ability to handle "either-or" scenarios in code.

3. Algorithmic pattern used

The "Array, Dynamic Programming interview pattern" is used here to maintain two arrays (or variables) as we iterate. Let noDeletion[i] be the maximum subarray sum ending at i with zero elements deleted. This is just standard Kadane’s. Let oneDeletion[i] be the maximum subarray sum ending at i where exactly one element has been deleted. To calculate oneDeletion[i], you either take noDeletion[i-1] (meaning you just deleted the current element arr[i]) or oneDeletion[i-1] + arr[i] (meaning you already deleted an element earlier).

4. Example explanation

Consider the array [5, -10, 6].

• At index 0 (5): noDel = 5, oneDel = 0 (or some small value).
• At index 1 (-10):
  • noDel = max(-10, 5 + (-10)) = -5.
  • oneDel = max(noDel_prev, oneDel_prev + curr) = max(5, 0 - 10) = 5. (We "deleted" -10).
• At index 2 (6):
  • noDel = max(6, -5 + 6) = 6.
  • oneDel = max(noDel_prev, oneDel_prev + curr) = max(-5, 5 + 6) = 11. The global maximum is 11.

5. Common mistakes candidates make

The most common mistake in the "Maximum Subarray Sum with One Deletion coding problem" is not handling the "non-empty" constraint correctly. If the array is all negative, like [-1, -1, -1], you still have to pick at least one element (e.g., -1). Another error is failing to consider that deleting an element effectively "joins" the subarray from the left and the subarray from the right. While the two-variable DP approach is better, some candidates try a "left-sum and right-sum" approach and miss edge cases.

6. Interview preparation tip

Practice the "state-based" DP approach. Instead of thinking about the deletion as a one-time event that happens at a specific index, think of it as a state you can transition into. This makes the logic much more robust. Also, always check if your solution handles the case where no deletion is performed at all (since the problem says "at most" one deletion). Comparing your two DP states at every step is crucial for finding the true maximum.