Find pair with maximum Appeal value
Let $B[i] = A[i] + i$ and let $C[j] = A[j] - j$. You are looking for
$$
\max_{i \geq j} B[i] + C[j] = \max_j (C[j] + \max_{i \geq j} B[i]).
$$

This gives a linear time in-place algorithm for your problem:


maxB = A[n] + n
maxSum = A[n] - n + maxB
for j=n-1 downto 1:


maxB = max(maxB, A[j] + j)
candidate = A[j] - j + maxB
maxSum = max(candidate, maxSum)

return maxSum