Delete and Concatenate

The key is to stop thinking about a long sequence of deletions and instead ask what one pair operation actually does to the contributions of its two elements.

Rewriting an operation

For every element, define

$$b_i=a_i-c.$$

If $a_i$ is removed alone, its contribution is exactly $b_i$.

Now consider a pair with values $x\le y$. Removing it contributes

$$\max(x,y)-c=y-c.$$

We can rewrite this as

$$0+(y-c).$$

So the larger element contributes exactly what it would have contributed as a singleton, while the smaller element contributes zero.

Equivalently, compared with deleting both separately,

$$(y-c)-\bigl((x-c)+(y-c)\bigr)=c-x=-(x-c).$$

Pairing therefore erases the shifted contribution $x-c$ of the smaller element. It helps precisely when $x<c$, because then that erased contribution was negative.

What must be optimized?

Suppose a complete strategy uses $p$ pair operations. Choose one smaller element from every pair, breaking ties arbitrarily, and call these elements discarded. Every other element is kept.

The final score is

$$\sum_{i\notin D} b_i =\sum_{i=1}^{n}b_i-\sum_{i\in D}b_i,$$

where $D$ is the set of discarded elements and $|D|=p$.

Each pair consumes two elements, so

$$p\le m=\left\lfloor\frac n2\right\rfloor.$$

If we temporarily ignore adjacency and the requirement that a discarded element needs a larger partner, the best choice is obvious:

• Never discard a positive $b_i$; replacing it by zero would lower the score.
• Discard as many negative $b_i$ values as possible, up to $m$.
• If there are too many negative values, discard the smallest ones, since they hurt the most.

Sort the elements so that

$$b_1\le b_2\le\dots\le b_n.$$

Subtracting the same $c$ from every value does not change their order, so sorting either $a_i$ or $b_i$ is equivalent. The resulting upper bound is

$$\boxed{ \sum_{i=1}^{m}\max(b_i,0)+\sum_{i=m+1}^{n}b_i }.$$

The first $m$ contributions are allowed to become zero when negative; all remaining contributions stay as they are.

Why adjacency does not screw up the greedy choice

Sorting is only used to identify which values we want to discard. We are not claiming that the operation can reorder the array. That would be rather illegal.

Let $D$ contain the negative values among the first $m$ sorted elements. Suppose $|D|=k$. These are the $k$ globally smallest values, and $k\le m$. Let $K$ contain all other elements. Then:

• $|K|=n-k\ge k=|D|$;
• every value in $K$ is at least every value in $D$.

Return to the elements' original order and label each one either D or K. While a D remains, a K also remains because there are at least as many K elements. Any linear sequence containing both labels has some adjacent pair with different labels. Remove that adjacent D-K pair.

The K value is at least the D value, so the pair contributes the shifted value of K, while D contributes zero, exactly as desired. Removing one element of each type preserves the inequality between their remaining counts. Repeat until no D remains, then remove every remaining K as a singleton.

Thus the supposedly relaxed upper bound is actually achievable. The changing adjacency created by concatenation is exactly what makes this work.

Correctness proof

Lemma 1. In any strategy, every pair operation replaces the shifted contribution of one of its smaller elements by zero, while all other elements contribute $b_i=a_i-c$.

Proof. For a pair $x\le y$, its contribution is $y-c=0+(y-c)$. A singleton contributes its own value minus $c$. Summing this identity over all operations gives the claim. $\square$

Lemma 2. No strategy scores more than

$$A=\sum_{i=1}^{m}\max(b_i,0)+\sum_{i=m+1}^{n}b_i,$$

where the $b_i$ are sorted and $m=\lfloor n/2\rfloor$.

Proof. By Lemma 1, a strategy can erase at most one shifted contribution per pair, hence at most $m$ contributions total. Among at most $m$ values, erasing the smallest negative ones gives the largest possible improvement. This is exactly what the formula for $A$ does. Any actual pairing restrictions can only make this relaxed optimum smaller, so every strategy is bounded by $A$. $\square$

Lemma 3. There exists a valid sequence of operations scoring exactly $A$.

Proof. Mark the negative values among the first $m$ sorted elements as discarded. They form a prefix of the sorted values, so every unmarked value is at least every marked value. There are at most $m$ marked elements and therefore at least as many unmarked elements.

As long as a marked element remains, choose an adjacent boundary between a marked and an unmarked element and remove that pair. The unmarked value is the maximum and contributes its $b_i$; the marked value contributes zero. Eventually every marked element is removed this way. Remove all remaining unmarked elements singly. The resulting contribution is zero for exactly the selected negative values and $b_i$ for every other value, totaling $A$. $\square$

Theorem. The algorithm outputs the maximum possible final score.

Proof. Lemma 2 proves that the algorithm's value is an upper bound on every strategy. Lemma 3 constructs a valid strategy attaining that value. Therefore it is optimal. $\square$

Complexity

Sorting costs $O(n\log n)$ time, and the final scan costs $O(n)$. The array uses $O(n)$ memory. All arithmetic must use 64-bit integers: the answer can have magnitude around $4\cdot10^{14}$.

For example, with $a=[1,3,1]$ and $c=2$, the sorted shifted values are $[-1,-1,1]$. Since $m=1$, only one negative contribution can be erased, giving $0+(-1)+1=0$. You cannot erase both negatives with one winner; pairs are useful, not magical.