Trip planning algorithm

Question

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 < A.length; i++) {
    for (int j = 0; j < A.length; j++) {
        int currentAppeal = A[i] + A[j] + (i - j);
        highestAppeal = currentAppeal > 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?

Answer 1

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 < 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 < A.length; i++) {
        for (int j = 0; j <= 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.

Answer 2

Yesterday, I asked the interviewers themselves for an efficient solution to this problem, and I finally got one:

int maxStart = A[0];
int maxEnd = A[0];

for (int i = 0; i < A.length; i++) {
    if ((A[i] - i) > maxStart) {
        maxStart = A[i] - i;
    }

    if ((A[i] + i) > maxEnd) {
        maxEnd = A[i] + i;
    }
}

return maxEnd + maxStart;

So this is the O(n) solution they gave me, which I found pretty beautiful to be honest.