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.

class Solution:
    def maximumSum(self, arr: list[int]) -> int:
        n = len(arr)
        
        # left[i]: max sum of subarray ending at i without deletion
        left = [0] * n
        
        # right[i]: max sum of subarray starting at i without deletion
        right = [0] * n
        
        # Calculate left array
        left[0] = arr[0]
        max_so_far = arr[0]
        for i in range(1, n):
            left[i] = max(arr[i], left[i-1] + arr[i])
            max_so_far = max(max_so_far, left[i])
        
        # Calculate right array
        right[n-1] = arr[n-1]
        curr_max = arr[n-1]
        for i in range(n-2, -1, -1):
            right[i] = max(arr[i], right[i+1] + arr[i])
            curr_max = max(curr_max, right[i])
        
        # Calculate max sum with one deletion
        max_sum = max_so_far  # Initialize with max sum without deletion
        for i in range(1, n-1):
            max_sum = max(max_sum, left[i-1] + right[i+1])
            
        return max_sum

Explanation:

1. Problem Understanding:

   • Given an array of integers, find the maximum sum of a non-empty subarray after deleting at most one element.

2. Naive Approach:

   • A brute force approach would involve iterating through all possible subarrays, and for each subarray, trying all possible single element deletions, and keeping track of the maximum sum. This would have a time complexity of O(n^3), which would not be efficient for larger arrays.

3. Optimal Approach:

   • The optimal approach uses dynamic programming to solve this problem in O(n) time complexity.
   • We use two arrays, left and right.
     • left[i] stores the maximum subarray sum ending at index i without any deletions.
     • right[i] stores the maximum subarray sum starting at index i without any deletions.
   • Then, for each index i (excluding the first and last), we consider the possibility of deleting the element at i. The maximum subarray sum with one deletion can be calculated as left[i-1] + right[i+1]. This represents the sum of the maximum subarray ending at i-1 and the maximum subarray starting at i+1, effectively deleting element i.
   • The overall maximum sum will be the maximum of max_so_far (maximum subarray sum without deletion) and the maximum sum calculated by considering each element's deletion.

4. Code Implementation Details:

   • The code first calculates the left and right arrays using Kadane's algorithm.
   • Then, it iterates from the second element to the second-to-last element in the array and computes the maximum possible sum by potentially deleting each element.
   • The max_sum variable is updated to store the maximum sum found so far.

Example Walkthrough:

For arr = [1, -2, 0, 3],

1. left array will be computed as [1, -1, 0, 3]
2. right array will be computed as [1, 0, 3, 3]
3. Then, we try to delete:
   • -2: max sum will be left[0] + right[2] = 1 + 3 = 4
   • 0: max sum will be left[1] + right[3] = -1 + 3 = 2
4. The maximum value in left and right are also considered which are 1, 0, 3 and 1,0,3,3 respectively.
5. Thus, the maximum sum is 4.

Edge Cases:

1. All Negative Numbers:

   • If all numbers are negative, the algorithm will return the largest negative number (i.e., the least negative number), which corresponds to the maximum possible sum of a non-empty subarray.

2. Single Element Array:

   • If the array contains only one element, there is no possibility of deletion, and the algorithm should return that element.

3. Array with Zeros:

   • Zeros do not affect the algorithm's correctness. The Kadane's algorithm correctly handles zeros in the array.

4. Empty Array:

   • The problem statement indicates that the array will not be empty, so this is not considered.

Big(O) Run-time Analysis:

• Calculating the left array takes O(n) time.
• Calculating the right array takes O(n) time.
• Iterating through the array to find the maximum sum with deletion takes O(n) time.
• Therefore, the overall time complexity is O(n).

Big(O) Space Usage Analysis:

• The left array requires O(n) space.
• The right array requires O(n) space.
• Therefore, the overall space complexity is O(n).