I'm not sure that linear time is possible for the problem as you have described it. 

I have a way to make it faster though:

Go through the array once and find the largest value in \$A\$, label it \$A_p\$ . Make sure you keep track of the largest and smallest \$p\$ if there are duplicate values. Then let $$G^* = 2A_p+  p_{max} - p_{min}$$.

This is our greedy guess at the maximum sum that we will use as a starting point. 

Next we want to find a lower bound on \$j\$ to limit our search space for any given \$i\$:    $$A_i+A_j+j-i > G^* \Leftrightarrow j > G^* +i-A_i-A_j$$

Unfortunately we can't have \$A_j\$  in the calculation of the bound of \$j\$ as that wouldn't be possible to compute. But note that if we replace \$A_j\$ with \$A_p\$ which is at least as large, then we will only lower the bound on \$j\$ and we will not miss any solutions. 

At this point we can start scanning of \$A\$ and update \$G^*\$ as we go to have higher and higher lower bounds on \$j\$ as we go. 

Technically this is still \$O(n^2)\$ but with a smaller constant as you are able progressively take larger and larger skips.