0
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – j_random_hacker Aug 21 at 22:40
  • $\begingroup$ Has been asked and answered before. $\endgroup$ – Yuval Filmus Sep 2 at 20:01
0
$\begingroup$

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:
    1. maxB = max(maxB, A[j] + j)
    2. candidate = A[j] - j + maxB
    3. maxSum = max(candidate, maxSum)
  • return maxSum
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.