<s>I'm not sure that linear time is possible for the problem as you have described it.</s> It is, see accepted answer.

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. 

Pseudocode:

    int G = A_p*2 + p_max - p_min;
    for(int i = 0; i < N; ++i){
        int j_start = max(i, G + i - A_p -A[i]);
        for(int j = j_start; j < N; ++j){
            int s = A[i] + A[j] + j - i;
            if( s > G){
                G = s; // You could check if you can skip ahead on J here.
            }
        }
    }
    return G;