Maximum Sum Subarray with One Deletion

You are given an array of n integers. Your task is to find the maximum sum obtainable from a non-empty contiguous subarray after optionally deleting at most one element from it. Note that after deletion, the subarray must remain non-empty.

More formally, given an array \(a_1, a_2, \dots, a_n\), you may choose a contiguous subarray and, if you wish, remove exactly one element from it. The goal is to maximize the sum of the resulting subarray.

Consider the following examples:

• For \(a = [1, -2, 0, 3]\), the answer is 4.
• For \(a = [1, -2, -2, 3]\), the answer is 3.
• For \(a = [-1, -1, -1, -1]\), the answer is -1.

inputFormat

The input is given via stdin with the following format:

1. The first line contains a single integer n — the number of elements in the array.
2. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single integer representing the maximum sum obtainable from any non-empty subarray after at most one deletion. The output should be printed to stdout.

4
1 -2 0 3

4