Problem Brief

Maximize the Array Value

An array is given. In one operation, you can delete one element and then add the elements which are present to the left and right of it. You can also delete elements which are present at index 0 and the last index. Perform this operation until only one element is left. The goal is to perform the operations in such a way that you get the maximum element as the answer.

1Example 1

Input

arr = [-2, 4, 3, -2, -1]

Output

Explanation

Let's say we remove -2 at index 3, then the array would be [-2, 4, 2] (adding elements present at index 2 and 4). Now, removing the element from index 0, the array would be [4, 2]. Now, removing the element from index 1, the array would be [4]. The final answer is 4.

So basically, repeat this operation until only one element is left. That would be your answer. Perform these operations in such a way that you get the maximum element as the answer.

Constraints

Limits and guarantees your solution can rely on.

The size of the array could be up to 10^5.
-10^9 <= arr[i] <= 10^9

Draft autosaves locally

public int maximizeArrayValue(int[] arr) {
    // write your code here
}

Input

arr

[-2, 4, 3, -2, -1]

Output