Trip planning algorithm
Thinking this more, there are three things affecting the appeal.


A[i]
A[j]
i - j


Since A[i] + A[j] is the same as A[j] + A[i], you don't need to traverse the whole array in the inner loop.

Since the third component increases the appeal only when j &lt; i, you can restrict the inner loop to run from 0 to i.

You also need to take into account the fact that all cities may have negative appeal. Integer.MIN_VALUE is safe initial value, as the lowest valid value (2 * -1000000000 - 100000) is still greater than that.

Using Math.max would have been more readable.

    int highestAppeal = Integer.MIN_VALUE;

    for (int i = 0; i &lt; A.length; i++) {
        for (int j = 0; j &lt;= i; j++) {
            final int currentAppeal = A[i] + A[j] + (i - j);
            highestAppeal = Math.max(highestAppeal, currentAppeal);
        }
    }

    return highestAppeal; 


And you can't overestimate the value of commented code in an interview answer.