Maximum Subarray Sum with One Deletion
Given an array of integers arr, return the maximum sum for a non-empty subarray of contiguous elements with at most one element deletion.
In other words, choose a subarray and optionally delete one element from it so that:
- There is still at least one element left after the deletion.
- The sum of the remaining elements is as large as possible.
Note that the subarray must be non-empty after deleting one element.
Example 1
Input
arr = [1,-2,0,3]Output
4We can choose [1, -2, 0, 3] and drop -2, making [1, 0, 3] with sum 4.
Example 2
Input
arr = [1,-2,-2,3]Output
3Choosing [3] gives the maximum sum of 3.
Constraints
- 1 <= arr.length <= 10^5
- -10^4 <= arr[i] <= 10^4