{x}
blog image

Maximum Subarray Sum with One Deletion

Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion. In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.

Note that the subarray needs to be non-empty after deleting one element.

 

Example 1:

Input: arr = [1,-2,0,3]
Output: 4
Explanation: Because we can choose [1, -2, 0, 3] and drop -2, thus the subarray [1, 0, 3] becomes the maximum value.

Example 2:

Input: arr = [1,-2,-2,3]
Output: 3
Explanation: We just choose [3] and it's the maximum sum.

Example 3:

Input: arr = [-1,-1,-1,-1]
Output: -1
Explanation: The final subarray needs to be non-empty. You can't choose [-1] and delete -1 from it, then get an empty subarray to make the sum equals to 0.

 

Constraints:

  • 1 <= arr.length <= 105
  • -104 <= arr[i] <= 104

Solution Explanation: Maximum Subarray Sum with One Deletion

This problem asks to find the maximum sum of a contiguous subarray in an array, allowing for the deletion of at most one element. The optimal approach involves a combination of dynamic programming concepts and efficient array traversals.

Approach: Preprocessing and Enumeration

The core idea is to preprocess the array to efficiently compute the maximum subarray sum starting from each index and ending at each index. Then, we enumerate all possible deletion points to find the maximum sum after deleting at most one element.

  1. Preprocessing:

    • We create two arrays, left and right, of the same size as the input array arr.
    • left[i] stores the maximum sum of a subarray ending at index i. This is calculated using Kadane's algorithm (a dynamic programming approach). The maximum subarray ending at i is either arr[i] itself or the sum of arr[i] and the maximum subarray ending at i-1.
    • Similarly, right[i] stores the maximum sum of a subarray starting at index i. This is computed using Kadane's algorithm in reverse order (from the end of the array).

  2. Enumeration and Deletion:

    • We initialize the maximum sum ans to the maximum value in left (which represents the maximum subarray sum without any deletions).
    • We iterate through the array from index 1 to n-2 (excluding the first and last elements, as deleting these would lead to an empty subarray). For each index i:
      • We calculate the sum left[i-1] + right[i+1]. This represents the maximum sum of a subarray if we delete the element at index i.
      • We update ans to be the maximum of ans and this newly calculated sum.

  3. Return Value:

    • Finally, we return ans, which represents the maximum subarray sum with at most one deletion.

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the input array. This is because we traverse the array three times: once for calculating left, once for calculating right, and once for enumerating deletion points. Each traversal takes linear time.
  • Space Complexity: O(n) due to the use of left and right arrays to store the preprocessing results.

Code Examples (Python, Java, C++, Go, TypeScript, Rust)

The code examples in the original response demonstrate this approach effectively. Each example follows the same algorithm: preprocessing with Kadane's algorithm to find the maximum subarray sums from the left and right, and then iterating to consider deleting each element. Note that the max function is used extensively to find the maximum of multiple values. The choice of language only changes the syntax, not the underlying algorithm.