Find the highest result between two elements in an array using their values and indices
This is not a review, but an extended comment.

Consider the question:


  Given two arrays, A and B, find the maximum of A[i] + B[j]


I suppose you can do it in linear time.

Now rearrange the original equation as (A[k] - k) + (A[j] + j) and consider two auxiliary arrays, formed by A[i] - i and A[i] + i.

Finally realize that you don't need these arrays at all.