DSA problem
Maximum Subarray Sum with One Deletion
Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion.
In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.
Note that the subarray needs to be non-empty after deleting one element. This is a two-state extension of Kadane's Algorithm: at each index we track the best sum ending here with no deletion used and with one deletion used.
Examples
Example 1
Input:
arr = [1,-2,0,3]Output:
4Explanation: We can choose [1,-2,0,3] and drop -2, leaving [1,0,3] which sums to 4.
Example 2
Input:
arr = [1,-2,-2,3]Output:
3Explanation: We just choose [3] and do not delete anything to get a sum of 3.
Example 3
Input:
arr = [-1,-1,-1,-1]Output:
-1Explanation: The final subarray must be non-empty after the deletion, so the best we can do is a single element of -1.
Constraints
- 1 <= arr.length <= 10^5
- -10^4 <= arr[i] <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.