# 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 < 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?

• Well, I've added the expected function signature, so it is clear that an int is expected as result. – Power_of_zero Apr 9 at 12:13
• Ah, sorry, missed that. – TorbenPutkonen Apr 9 at 12:16
• I deleted my answer. I've come to the conclusion that this was a trick question with a purpose of finding out if you notice bad requirements and are able to ask clarifications. – TorbenPutkonen Apr 9 at 12:24
• I had lots of things to ask clarification for, but they sent me as an assignment through a site. I had 2 tasks which I had to do in 1 hour. This was one of them. – Power_of_zero Apr 9 at 12:25
• So, had no contact or any way of asking anything. – Power_of_zero Apr 9 at 12:26

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;


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.