Range Operation

Let the original array sum be $S$. If we choose a range $[l,r]$, every element in it becomes $l+r$, so the new sum is

$$S-\sum_{i=l}^{r}a_i+(r-l+1)(l+r).$$

So we only need to maximize the gain:

$$\text{gain}(l,r)=(r-l+1)(l+r)-\sum_{i=l}^{r}a_i.$$

Since the operation is optional, the final answer is

$$S+\max(0, \max_{1\le l\le r\le n}\text{gain}(l,r)).$$

The key algebra trick

The expression $(r-l+1)(l+r)$ looks annoying, but it collapses cleanly:

$$(r-l+1)(l+r)=r(r+1)-l(l-1).$$

You can verify it by expanding both sides:

$$(r-l+1)(l+r)=r^2+r-l^2+l.$$

And

$$r(r+1)-l(l-1)=r^2+r-l^2+l.$$

Same thing. Very convenient. Suspiciously convenient, even.

Now define prefix sums:

$$p_i=a_1+a_2+\dots+a_i,$$

with $p_0=0$. Then

$$\sum_{i=l}^{r}a_i=p_r-p_{l-1}.$$

Plug that into the gain:

$$\text{gain}(l,r)=r(r+1)-l(l-1)-(p_r-p_{l-1}).$$

Rearrange:

$$\text{gain}(l,r)=\bigl(r(r+1)-p_r\bigr)-\bigl(l(l-1)-p_{l-1}\bigr).$$

Now the expression splits into:

• a part depending only on $r$;
• a part depending only on $l$.

That means for each fixed right endpoint $r$, the best left endpoint $l$ is simply the one minimizing

$$l(l-1)-p_{l-1}$$

among all $l\le r$.

Algorithm

Scan $r$ from $1$ to $n$.

Before evaluating endpoint $r$, make sure the candidate left endpoint $l=r$ is available. Its value is

$$r(r-1)-p_{r-1}.$$

Maintain

$$\text{bestLeft}=\min_{1\le l\le r}\bigl(l(l-1)-p_{l-1}\bigr).$$

Then the best gain for ranges ending at $r$ is

$$r(r+1)-p_r-\text{bestLeft}.$$

Track the maximum gain over all $r$.

Finally print:

$$p_n+\max(0,\text{bestGain}).$$

Why this is correct

Every possible operation corresponds to exactly one pair $(l,r)$ with $l\le r$. For that pair, the gain formula above is exact.

For a fixed $r$, the term $r(r+1)-p_r$ is fixed. So maximizing the gain is equivalent to minimizing

$$l(l-1)-p_{l-1}$$

over all valid $l\le r$.

The scan maintains exactly that minimum before computing the answer for each $r$. Therefore, for every right endpoint, we consider the best possible left endpoint. Taking the maximum over all $r$ considers every range. Since we also compare against doing nothing with gain $0$, the optional operation is handled too.

Complexity

Each test case is processed in one pass.

Time complexity: $O(n)$

Memory complexity: $O(n)$ if storing prefix sums, or $O(1)$ extra with a running prefix. The implementation below uses the simple running-prefix version.