Find pair with maximum Appeal value Find pair with maximum Appeal value.


Input: Array
Output: index {i, j} ( i = j allowed) with maximum Appeal
Appeal = A[i] +A[j] + abs(i-j)


Example 1:


Input: [1, 3, -1]
Output: [1, 1]
Explanation: Appeal = A[1] + A[1] + abs(0) = 3 + 3 + 0 = 6


Example 2:


Input: [1, 6, 1, 1, 1, 1, 7]
Output: [1, 6]
Explanation 6 + 7 + abs(1 - 6) = 18


Example 3:


Input: [6, 2, 7, 4, 4, 1, 6]
Output: [0, 6]
Explanation: 6 + 6 + abs(0 - 6) = 18


I'm not sure how to approach this problem. I've tried the 2 pointer approach as below and it seems to work for some cases but I'm missing some fundamental intuition about it.

public static int[] maximumAppeal(int[] A) {
    int left = 0;
    int right = A.length - 1;
    int max = 0;
    int[] r = {-1,-1};
    while (left &lt;= right) {
        int sum = A[left] + A[right] + Math.abs(left - right);
        if (A[left] &lt;= A[right]) {
            if (sum &gt; max) {
                max =sum;
                r[0] = left;
                r[1] = right;
            }
            left++;
        } else {
            if (sum &gt; max) {
                max = sum;
                r[0] = left;
                r[1] = right;
            }
            right--;
        }
    }
    return r;
}


Edited:
Here's the link, its an Amazon question
https://leetcode.com/discuss/interview-question/355698
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