#1186
Maximum Subarray Sum with One Deletion
specialist · 915 · lc medium +31 · verified · 46.8% accepted · 2,020 likes · top 31%
Description
Given an integer array, find the maximum possible sum over any non-empty contiguous subarray, where you may optionally remove at most one element. At least one element must remain after any deletion.
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.
Code
1
2
3