# 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 <= right) {
int sum = A[left] + A[right] + Math.abs(left - right);
if (A[left] <= A[right]) {
if (sum > max) {
max =sum;
r[0] = left;
r[1] = right;
}
left++;
} else {
if (sum > 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

• This looks like a competition question -- please post a link to it, so that we can see if it's still live. Some of us prefer to help only when we can see that the question is not part of a live competition. – j_random_hacker Aug 21 '19 at 22:40
• Has been asked and answered before. – Yuval Filmus Sep 2 '19 at 20:01

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]).$$