Trip planning algorithm I was presented with an interview question described as follows:

Receiving an int[] A of cities, where each A[i] has an appeal value. We want to plan our trip based on the highest appeal possible, taking in mind that is calculated as follows A[i] + A[j] + (i - j). This means the appeal values of 2 cities summed, plus their distance.

Function signature:

public static int solution(int[] A);

The constraints were the following:


N is an integer within [1, 100,000]
A[i] is an integer within [-1,000,000,000, 1,000,000,000]


Using the same value is a possible valid solution, so for example, if we have A = {1, 3, -3}; this should return 6 as visiting city A[0] twice gives the max appeal value A[0] + A[0] + (0 - 0) = 6.

So given that, a possible solution is the same value twice, I did not found other solution than:

int highestAppeal = 0;

for (int i = 0; i &lt; A.length; i++) {
    for (int j = 0; j &lt; A.length; j++) {
        int currentAppeal = A[i] + A[j] + (i - j);
        highestAppeal = currentAppeal &gt; highestAppeal ? currentAppeal : highestAppeal;
    }
}

return highestAppeal;


This solution was marked as pretty bad. I realize that a \$O(n^2)\$ solution is far from efficient, but in this case, I did not see how to improve it. Later on, I thought about sorting A values in descending order and, for repeated values, using indexes in ascending order. But I don't see that going forward.

What would be a better and more efficient solution for this?
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.