Letter most:
For each lowercase letter count number of its occurrences in $$$s$$$, maximum of this value for all letters is the answer. All can be done in $$$O(n)$$$.
Array modification:
Assume will be the maximum. it can be proven that all operation should be done in direction of $$$$x$$$
Unable to parse markup [type=CF_MATHJAX]
for all operation on its left and $j = i — 1$ for all operations on its right).Now consider $pref_x$ is maximum value of $a_x$ if all operations be done in direction of right for all $i=1, 2, ..., x$. And consider $suf_x$ is maximum value of $a_x$ if all operations be done in direction of left for all $i=x, x+1, ..., n$.
It can bee seen that:
$$$pref_x = \frac{perf_{x-1}}{2} + a_x$$$.
$$$suf_x = \frac{suf_{x+1}}{2} + a_x$$$.
And so the answer is $max_{i=1}^{n}(pref_i + suf_i — a_i)$.
All can be done in $O(n)$.
