Farewell

Suppose the element initially at position $i$ is the one that remains. Exactly $i-1$ elements to its left and $N-i$ elements to its right are deleted. Its final value is therefore

$$A_i-(i-1)+(N-i)=A_i+N+1-2i,$$

regardless of the deletion order.

Evaluate this expression at every position $i$ and take the maximum. Each expression can be evaluated as its element is read, keeping only the largest value seen so far. The time complexity for one case is $O(N)$ and the auxiliary space complexity is $O(1)$.

Proof

While one element is kept until the end, its relative order with respect to every other element never changes. Deleting an element that was initially to its left decreases its value by $1$, and deleting an element that was initially to its right increases its value by $1$. Every other element is deleted exactly once, so the element initially at position $i$ always finishes with value $A_i+N+1-2i$.

For subtask $1$, exhaustive search can try every choice of an element to delete from the current sequence and examine all possible final values. Modify the sequence in place, and restore it after each recursive call. This takes $O(N!)$ time and $O(N)$ space for the sequence and recursion stack.

For subtask $2$, choose each candidate for the final element in turn and add the contribution of deleting every other element individually. This takes $O(N^{}$ time and space to store the sequence.