Linear time algorithm for finding shifted max
We can compute $m$ in linear time.

For simplicity suppose that the arrays are 0 based: $A[0..n-1]$, $B[0..n-1]$. 
We want to compute $m = \max_i B[i]+i$.

Let $max = \max_i A[i]$. 
Obviously $max \leq m$.

Let $A[j]$ be $B[k]$ after sorting. If $A[j] \leq max - n$ we have
$$B[k] + k \leq B[k] + (n-1) = A[j] + (n-1) \leq (max-n) + (n-1) = max-1 &lt; max \leq m.$$

Therefore we can ignore $A[j]$ when $A[j] \leq max - n$. 
We only need to consider the numbers in the range $[max-n, max]$.

We can use counting sort to sort the numbers in $A$ 
which are in the range $[max-n, max]$ in linear time and
use the sorted list to compute $m$.