### PROBLEM LINK:

**Author:** Sergey Kulik

**Testers:** Kevin Atienza and Vasya Antoniuk

**Translators:** Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)

**Editorialist:** Kevin Atienza

### DIFFICULTY:

Easy

### PREREQUISITES:

Maximum Subarray Sum

### PROBLEM:

Given an array A[1\ldots N], what is the maximum **subarray sum** you can get by removing at most one element?

### QUICK EXPLANATION:

For every position i, compute the maximum subarray sum that ends in position i. Call it E[i].

For every position i, compute the maximum subarray sum that starts in position i. Call it S[i].

Both can be done in O(N) using Kadaneâ€™s algorithm/dynamic programming.

The answer is the largest among the following values:

- The maximum in E.
- The maximum E[i-1] + S[i+1] for every position 1 < i < N.

### EXPLANATION:

# No removals

Letâ€™s first answer a simpler question: What is the maximum subarray sum of the array (without any removals)? This is actually a standard problem and you might already be familiar with it, but letâ€™s describe it anyway.

Hereâ€™s a naĂŻve solution (in pseudocode):

```
answer = -INFINITY
for j=1..N:
current = 0
for i=j..1 by -1:
current += A[i]
answer = max(answer, current)
```

It simply tries out all subarrays. Unfortunately, this is slow; it runs in O(N^2) time, and for N \approx 10^5 this will not pass the time limit.

To improve this solution, notice that we donâ€™t have to check *all* the subarrays that end at j. We can classify all such subarrays into two types: whether it has length 1 or length greater than 1.

- If it has length 1, then the sum is simply A[j].
- If it has length greater than 1, then we can break this subarray into two parts. The first part is
**a subarray that ends in j-1**, and the second is A[j] itself. Thus, in order to maximize the sum, we must choose the subarray that ends in j-1**with the maximum sum**.

That last part is crucial; if you study the code above more closely, notice that what weâ€™re computing is, for every possible rightmost index j, the maximum subarray sum that *ends in j*. And weâ€™re doing this in increasing order of j. Thus, when weâ€™re trying to compute it for j, we already have the answer for j-1, so we donâ€™t need a loop any more!

The following code illustrates it better:

```
answer = -INFINITY
current = 0
for j=1..N:
current = max(A[j], current + A[j])
answer = max(answer, current)
```

Notice that before the line `current = max(A[j], current + A[j])`

, the variable `current`

contains the maximum sum that ends in j-1. Thus, `current + A[j]`

is the maximum sum of any subarray that ends in j with length greater than 1.

This is now much faster: it runs in O(N) time! Also, if youâ€™re curious, this algorithm is actually famous and has a name: **Kadaneâ€™s algorithm.**

**Implementation notes:**

- Note that \left|A[i]\right| can reach up to 10^9, so
`current`

and`answer`

will exceed the bounds for 32-bit integers. So you should use 64-bit variables (`long long`

in C/C++,`long`

in Java). - For
`INFINITY`

, you can use a very large number that will exceed all finite numbers under consideration. Since the maximum absolute sum is only 10^5\cdot 10^9 = 10^{14}, an`INFINITY`

value of, say, 10^{18} is good enough for our purposes!

# One removal

Now, letâ€™s answer the original problem, where you are allowed to remove at most one element from the array. We already know the answer when you donâ€™t remove any element, so all that remains it to compute the answer if we remove *exactly one* element. The maximum among these two is the answer. More specifically,

- Let M_0 be the answer if you donâ€™t remove any element, and
- Let M_1 be the answer if you remove one element.

Then the answer is \max(M_0, M_1). We already know M_0 from above, so all that remains is computing M_1.

Obviously, we can try removing each element in turn, and computing the maximum subarray sum, and obtaining M_1 as the maximum among all these maximums. But this takes O(N^2) time which is too slow. We will need a better algorithm.

Suppose we remove the element A[i]. Then there are only three possible cases for the maximum subarray sum:

- The maximum subarray is completely to the left of A[i].
- The maximum subarray is completely to the right of A[i].
- The maximum subarray contains A[i-1] and A[i+1].

But hereâ€™s an important observation: in the first two cases, *the subarrays are actually also subarrays of the original array*, which means their sums cannot be more than M_0. And since weâ€™re trying to maximize the answer and we alreaady know that the answer is \ge M_0, we can safely ignore these cases!

So all that remains is computing the maximum sum of any subarray that contains A[i-1] and A[i+1] (ignoring A[i] of course). We can decompose such a subarray into two parts:

- A subarray that ends in A[i-1], and
- A subarray that starts at A[i+1].

These two subarrays donâ€™t overlap, so in order to maximize the sum, we want to maximize them individually. But *we have already computed all maximum subarray sums that end in every position*, from the previous algorithm! So if we just store the partial results that we got, then we can answer the first part quickly!

In more detail, let E[i] be the maximum subarray sum that ends in A[i]. We can compute E[1\ldots N] using the previous algorithm:

```
answer = -INFINITY
current = 0
for j=1..N:
current = max(A[j], current + A[j])
answer = max(answer, current)
E[j] = current
```

Similarly, we can define S[i] to be the maximum subarray sum that *starts* at A[i]. Computing S[1\ldots N] by performing the algorithm *in reverse*, as in the following:

```
current = 0
for j=N..1 by -1:
current = max(A[j], current + A[j])
answer = max(answer, current)
S[j] = current
```

With arrays S[1\ldots N] and E[1\ldots N], we can now compute the maximum sum of any subarray that contains A[i-1] and A[i+1], assuming A[i] is removed: It is simply E[i-1] + S[i+1]!

```
for i=2..N-1:
answer = max(answer, E[i-1] + S[i+1])
```

By combining all these snippets, we now have the answer to the problem!

### Time Complexity:

O(N)