You are given an integer array A. You can delete at most one element from the array. Find the maximum possible sum of a non-empty subarray after performing at most one deletion. This models real scenarios where removing one bad data point improves overall performance.

Why this is asked

• Tests dynamic thinking beyond Kadane

• Real use: analytics optimization

Example

Input:

1 -2 0 3

Output:

4

Key Concepts

• Modified Kadane’s algorithm

• Forward + backward DP