Find the highest result between two elements in an array using their values and indices 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&lt;Integer&gt; occoured = new HashSet&lt;Integer&gt;();
    int maxAppeal = 0;

    for(int i = 0; i &lt; A.length; i++) {
        if(occoured.add(A[i])) {
            for(int j = i; j &lt; A.length; j++) {
                int appeal = A[i] + A[j] + (j - i);
                if(appeal &gt; maxAppeal)
                    maxAppeal = appeal;
            }
        }
    }
    return maxAppeal;
}
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.