Maximum Subarray Sum with One Deletion

You are given an integer array nums. You want to choose a contiguous subarray of nums and, optionally, delete at most one element from within that subarray (not from its two ends unless you still keep the subarray contiguous after removal — conceptually the deleted element is simply skipped when summing). The subarray must contain at least one element after the optional deletion.

Return the maximum possible sum you can obtain by picking such a subarray and deciding whether to delete zero or one of its elements.

Rules to keep in mind:

• The subarray itself must be contiguous in the original array, but after removing the one chosen element, the remaining values are summed together (they no longer need to occupy contiguous positions in the original array).
• You are never required to delete an element — skipping the deletion is always a valid choice.
• The final result must consist of at least one number; you cannot delete every element in your chosen subarray.

Examples

Example 1:

Input: nums = [2, -5, 3, 1, -2, 4]

Output: 8

Explanation:

• Consider the subarray [3, 1, -2, 4]. Deleting the -2 leaves [3, 1, 4], which sums to 8.
• No other subarray, with or without a deletion, produces a higher total.

Example 2:

Input: nums = [-3, -2, -1]

Output: -1

Explanation:

• Every value is negative, so the best strategy is to take a subarray of length one, namely [-1], and perform no deletion (deleting it would leave nothing).
• Any two-element subarray would force you to either keep a larger negative sum or delete down to a single value, and -1 alone is still the best available number.

Example 3:

Input: nums = [1, -1, 1, -1, 1]

Output: 3

Explanation:

• Take the entire array [1, -1, 1, -1, 1] and delete one of the -1 values, leaving three 1s that sum to 3.

Constraints

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4