Linear time algorithm for finding shifted max Assume that we are given an array $A[1..n]$ containing nonnegative integers (not necessarily distinct).

Let $B$ be $A$ sorted in the nonincreasing order.
We want to compute 
$$m = \max_{i\in [n]} B[i]+i.$$

The obvious solution is sorting $A$ and then compute $m$. This gives an algorithm that runs in time $O(n \lg n)$ in the worst case.


  Is it possible to do better? Can we compute $m$ in linear time?




My main question is the one above.
But it would be interesting to know about the following generalization of the problem.

Let $B$ be $A$ sorted according to some comparison oracle $\leq$
and $f$ a function given by an oracle.
Given $A$ and oracles for $\leq$ and $f$, what can we say about the time needed to compute $m = \max_{i \in [n]} f(B[i],i)$?

We can still compute $m$ in $O(n \lg n)$ time. But can we prove a super-linear lower-bound for this generalized case? 

If the answer is yes does the lower-bound hold if we assume that $\leq$ is the usual order on integers and $f$ is a "nice" function (monotone, polynomial, linear, etc.)?
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$.