Subtask 1

Let $[S_1,\dots ,S_k]$ be non-decreasing and let $[S_{k+1},\dots ,S_N]$ be non-increasing.

For $S_i$ to be non-decreasing, we want $S_i\le S_{i+1}$. Thus we must add $max(0,S_i-S_{i+1})$ to $S_{i+1}$.

Similarly, for $S_i$ to be non-increasing, we want $S_i\ge S_{i+1}$. Thus we must add $max(0,S_{i+1}-S_i)$ to $S_i$.

Finally, either $S_k\le S_{k+1}$ or $S_k\ge S_{k+1}$, so we are done.

Doing this by iterating the array for each value of $k$ gives an $\mathcal{O}(N^2)$ solution.

Time Complexity: $\mathcal{O}(N^2)$

Subtask 2

Note that if $[S_1,\dots ,S_k]$ is non-decreasing, then $[S_1,\dots ,S_{k-1}]$ must also be non-decreasing. Thus we can precompute the amount of time it takes $[S_1,\dots ,S_k]$ to become non-decreasing for all $k$ in $\mathcal{O}(N)$.

By the same argument, we can precompute the amount of time it takes $[S_k,\dots ,S_N]$ to become non-increasing for all $k$ in $\mathcal{O}(N)$.

Iterating the array for each value of $k$ again, we obtain an $\mathcal{O}(N)$ solution.

Time Complexity: $\mathcal{O}(N)$

Alternate Solution

We present a greedy algorithm that solves the problem in $\mathcal{O}(N)$. We take advantage of the fact that it is never optimal to increment $a_k$ if $a_k=max(S)$.

1. Find an index $i$ such that $S_i=max(S)$.
2. Now make $[S_1,\dots ,S_i]$ non-decreasing and make $[S_i,\dots ,S_N]$ non-increasing.

Note that both steps take $\mathcal{O}(N)$ time and thus the overall algorithm also takes $\mathcal{O}(N)$ time.

Time Complexity: $\mathcal{O}(N)$