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 <= 10^5-10^4 <= arr[i] <= 10^4
## Maximum Subarray Sum with One Deletion
This problem asks us to find the maximum sum of a non-empty subarray after deleting at most one element from it. This means we need to consider subarrays with no deletions, and subarrays with one deletion, and choose the one with the maximum sum.
### 1. Brute Force Solution
A brute force solution would be to iterate through all possible subarrays, and for each subarray, try deleting each element and calculate the sum. Keep track of the maximum sum encountered.
```python
def max_subarray_deletion_brute_force(arr):
n = len(arr)
max_sum = float('-inf')
for i in range(n):
for j in range(i, n):
# Subarray arr[i:j+1]
subarray = arr[i:j+1]
# No deletion case
max_sum = max(max_sum, sum(subarray))
# Deletion cases
if len(subarray) > 1:
for k in range(len(subarray)):
temp_subarray = subarray[:k] + subarray[k+1:]
max_sum = max(max_sum, sum(temp_subarray))
return max_sum
Complexity Analysis:
- Time Complexity: O(n^3), where n is the length of the array.
- Space Complexity: O(n) due to subarray slicing.
This brute force approach is not efficient due to the nested loops.
2. Optimal Solution (Dynamic Programming)
We can solve this problem more efficiently using dynamic programming. We'll use two arrays:
left[i]: Maximum subarray sum ending at indexiwithout any deletion.right[i]: Maximum subarray sum starting at indexiwithout any deletion.
Then, we can iterate through the array and for each index i, consider deleting the element at that index. The maximum sum in this case would be left[i-1] + right[i+1]. We also need to consider the case where there's no deletion at all, which can be computed using Kadane's algorithm.
def max_subarray_deletion_optimal(arr):
n = len(arr)
# left[i]: Maximum subarray sum ending at index i without deletion
left = [0] * n
left[0] = arr[0]
max_so_far = arr[0]
current_max = arr[0]
for i in range(1, n):
current_max = max(arr[i], current_max + arr[i])
max_so_far = max(max_so_far, current_max)
left[i] = current_max
# right[i]: Maximum subarray sum starting at index i without deletion
right = [0] * n
right[n-1] = arr[n-1]
for i in range(n-2, -1, -1):
right[i] = max(arr[i], right[i+1] + arr[i])
max_sum = max_so_far # Maximum sum without any deletion
# Consider deletion at each index i
for i in range(1, n-1):
max_sum = max(max_sum, left[i-1] + right[i+1])
# Handle edge cases where deletion happens at the start or end
max_sum = max(max_sum, right[1])
max_sum = max(max_sum, left[n-2])
# If all numbers are negative, return the largest element
if max_sum <= 0:
return max(arr)
return max_sum
3. Optimized DP (Kadane's Algorithm with Deletion)
An even more efficient solution uses Kadane's algorithm with deletion capability during the scan.
def max_subarray_deletion_kadane(arr):
n = len(arr)
max_so_far = arr[0]
current_max_no_deletion = arr[0]
current_max_one_deletion = 0
for i in range(1, n):
current_max_one_deletion = max(current_max_no_deletion, current_max_one_deletion + arr[i])
current_max_no_deletion = max(arr[i], current_max_no_deletion + arr[i])
max_so_far = max(max_so_far, current_max_no_deletion, current_max_one_deletion)
if current_max_no_deletion < 0:
current_max_no_deletion = 0
if current_max_one_deletion < 0:
current_max_one_deletion = 0
if max_so_far == 0: # Handle all negative numbers
return max(arr)
return max_so_far
Big(O) Run-time Analysis
-
Optimal DP Solution:
- The
max_subarray_deletion_optimalfunction calculates theleftandrightarrays in O(n) time. The loop to find the maximum sum with deletion takes O(n) time as well. Therefore, the overall time complexity is O(n).
- The
-
Kadane's Algorithm with Deletion:
- The
max_subarray_deletion_kadanefunction scans the array once, performing constant-time operations at each index. Thus, the time complexity is O(n).
- The
Big(O) Space Usage Analysis
-
Optimal DP Solution:
- The
max_subarray_deletion_optimalfunction uses two arrays,leftandright, each of size n. Therefore, the space complexity is O(n).
- The
-
Kadane's Algorithm with Deletion:
- The
max_subarray_deletion_kadanefunction uses only a few constant space variables. Therefore, the space complexity is O(1).
- The
Edge Cases and Considerations
- All negative numbers:
- If the array contains only negative numbers, the algorithm should return the largest (least negative) number.
- Empty array:
- The problem statement specifies a non-empty subarray, so an empty array is not a valid input. However, if it were, we could return 0 or raise an exception.
- Single element array:
- If the array has only one element, that element should be returned as the maximum sum.
- Array with zeros:
- The algorithm handles zeros correctly, as they do not affect the maximum sum.
- Large arrays:
- For very large arrays, the O(n) time complexity of the optimal solutions is efficient, and no further optimization is typically needed.
Conclusion
The optimal approach using Kadane's algorithm is the most efficient in terms of both time and space complexity. It provides an O(n) time solution with constant space usage.
