Kadane, Minus One

Difficulty: 1600 4000 ms 128 MB

dp

Find the maximum sum of a non-empty contiguous subarray, where you may optionally delete AT MOST ONE element from within it (the remaining elements must stay contiguous in the original array).

Input: the first line has N; the second line has N integers.

Output: the best achievable sum.

Constraints:

• 1 ≤ N ≤ 10⁵
• |a_i| ≤ 10⁴

Sample Tests

5
1 -2 3 -1 4

7

1
-3

-3

Read the Editorial