Maximum Subarray Sum with One Deletion
Medium Kadane with two states
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the largest sum of a non-empty subarray when you are allowed to delete at most one element from it (it must stay non-empty).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: best subarray sum if you may delete one element from it.
Why this works: track two values per index: best sum ending here with no deletion, and with one deletion already used.
Example: [1, -2, 0, 3]
at 3: no-deletion best = 0 + 3 = 3with deletion of -2: 1 + 0 + 3 = 4answer 4
✦Hints open one at a time
↗Approach
keep = Kadane's value. del = max(previous keep (delete current), previous del + nums[i]). The answer is the max of both over all i. Initialise del very low so it never represents an empty subarray.
</>Solution (Java)
class Solution {
public int maximumSum(int[] arr) {
int keep = arr[0], del = Integer.MIN_VALUE / 2, best = arr[0];
for (int i = 1; i < arr.length; i++) {
int x = arr[i];
del = Math.max(keep, del + x); // delete x, or deleted earlier
keep = Math.max(x, keep + x); // plain Kadane
best = Math.max(best, Math.max(keep, del));
}
return best;
}
}!Common mistake
Letting the "deleted" state be an empty subarray, which wrongly returns 0 for all-negative input.
- Time: O(n).
- Space: O(1).