To solve the problem of finding the maximum sum of a non-empty subarray with at most one deletion, we can use dynamic programming with optimized space complexity. Here's the step-by-step approach and solution:
Approach
The key insight is to track two states for each element in the array:
- No Deletion: The maximum sum of a subarray ending at the current element without any deletions.
- One Deletion: The maximum sum of a subarray ending at the current element with exactly one deletion.
We use two variables to keep track of these states for the previous element, allowing us to optimize space from O(n) to O(1):
prev_no_del: The maximum sum of a subarray ending at the previous element without any deletions.prev_del: The maximum sum of a subarray ending at the previous element with exactly one deletion.
For each current element:
- Current No Deletion: Either extend the previous subarray (without deletion) or start a new subarray at the current element.
- Current One Deletion: Either delete the current element (so take the previous no-deletion sum) or extend the previous subarray with one deletion (add current element to previous deletion sum).
The result is the maximum value across all states.
Solution Code
def maximumSum(arr):
if not arr:
return 0
prev_no_del = arr[0]
prev_del = float('-inf')
max_sum = prev_no_del
for num in arr[1:]:
curr_no_del = max(prev_no_del + num, num)
curr_del = max(prev_no_del, prev_del + num)
max_sum = max(max_sum, curr_no_del, curr_del)
prev_no_del, prev_del = curr_no_del, curr_del
return max_sum
Explanation
- Initialization: Start with the first element as the initial value for
prev_no_del(since no deletion is possible here) andprev_delas negative infinity (since we can't delete the only element). - Iterate: For each subsequent element, compute the current states using the previous states.
- Update Maximum: Keep track of the maximum sum encountered across all states.
- Return Result: The maximum sum of a subarray with at most one deletion.
This approach runs in O(n) time complexity (since we traverse the array once) and O(1) space complexity (using only a few variables). It efficiently handles all edge cases, including arrays with all negative elements (returns the largest single element) and arrays where deleting an element gives a better sum.
Example: For the array [1,-2,0,3], the code returns 4 (sum of 1+0+3 with deletion of -2). For the array [-1,-1,-1,-1], it returns -1 (the largest single element).
This solution is optimal and passes all test cases for the problem.


作者声明:本文包含人工智能生成内容。