Maximum Subarray Sum with One Deletion
Problem statement
You are given an integer array arr. Choose one non-empty contiguous subarray. You may then delete at most one element from the chosen subarray, but at least one element must remain after the deletion.
Return the largest possible sum of the elements that remain.
Function
maximumSum(arr: int[]) → intExamples
Example 1
arr = [3,-4,5,1]return = 9Take the whole array and delete -4. The remaining elements 3, 5, 1 add up to 9. Without a deletion the best is 5 + 1 = 6.
Example 2
arr = [2,-1,-6,4]return = 5Take the whole array and delete -6: 2 + (-1) + 4 = 5. Only one element may be deleted, so -1 must stay. Any choice that avoids -6 without deleting it lies inside [2, -1] or [4]; the best of those is 4, which is smaller.
Example 3
arr = [-5,-2,-8]return = -2Every element is negative. At least one element must remain, so the best choice is the single element -2, with no deletion.
Constraints
1 <= arr.length <= 2 * 104-104 <= arr[i] <= 104