Maximum Subarray Sum With One Deletion

Reported in interviews at AQR Capital Management Hudson River Trading Susquehanna (SIG)

Problem statement

Given an array of integers $a_1, a_2, \ldots, a_n$ (which may contain negative values), find the maximum sum of a non-empty contiguous subarray, where you are allowed to delete at most one element from the chosen subarray.

Note that after deleting an element, the remaining elements on the left and right are treated as joined: their sum is what counts. The non-emptiness requirement applies to what is left after the optional deletion -- at least one element must survive. So a one-element subarray simply cannot use its deletion, and for an all-negative array the best you can do is the single largest element.

Constraints:

  • $1 \leq n \leq 10^5$
  • $-10^4 \leq a_i \leq 10^4$

Example 1:

  • Input: $a = [1, -2, 0, 3]$
  • Output: $4$
  • Explanation: Choose the subarray $[1, -2, 0, 3]$ and delete $-2$ to get sum $1 + 0 + 3 = 4$.

Example 2:

  • Input: $a = [1, -2, -2, 3]$
  • Output: $3$
  • Explanation: Choose the subarray $[3]$. No deletion needed.

Example 3:

  • Input: $a = [-1, -1, -1, -1]$
  • Output: $-1$
  • Explanation: All elements are negative. The best we can do is pick the single largest element. Deleting does not help because we must keep at least one element.

Design an $O(n)$-time, $O(1)$-space algorithm.

Show hint

What does the classic running-best-sum algorithm track at each position, and what extra fact about the past would you need to know to allow one removal?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems