Find the highest result between two elements in an array using their values and indices

Question

I got a programming question on an interview where performance was the focus. I couldnt come up with a better solution than the one below which I think has a time complexity of O(n^2 + n) and scored 20/100 on performance.

The question in short was to find the highest result by adding two elements and in an array and the difference between the two indices e.g A[k] + A[j] + (j - k) - (k can be equal to j).

The size of the array = [1...100 000]
The values in the array =[-1000 000 000...1000 000 000]

I know using nested loops usally is a bad idea when It comes to handling larger arrays. So my question is simply how can it be improved to make it faster?

public static int solution(int [] A) {
 Set<Integer> occoured = new HashSet<Integer>();
 int maxAppeal = 0;
 for(int i = 0; i < A.length; i++) {
 if(occoured.add(A[i])) {
 for(int j = i; j < A.length; j++) {
 int appeal = A[i] + A[j] + (j - i);
 if(appeal > maxAppeal)
 maxAppeal = appeal;
 }
 }
 }
 return maxAppeal;
}

Answer 1

This is not a review, but an extended comment.

Consider the question:

Given two arrays, A and B, find the maximum of A[i] + B[j]

I suppose you can do it in linear time.

Now rearrange the original equation as (A[k] - k) + (A[j] + j) and consider two auxiliary arrays, formed by A[i] - i and A[i] + i.

Finally realize that you don't need these arrays at all.