Find maximum value of Point represented by an Array of values for each coordinate Suppose there is an array A = {3,2,5}, then points for this array correspond to indexes (i,j) where i &lt;= j = {(0,0), (0,1), (0,2), (1,1), (1,2), (2,2)}. The program returns max(sum) such that sum = A[i] + A[j] + (j - i). For the above array :


point (0,0) will have sum = (3 + 3) + (0 - 0) = 6
point (0,1) will have sum = (3 + 2) + (1 - 0) = 6
point (0,2) will have sum = (3 + 5) + (2 - 0) = 10
point (1,1) will have sum = (2 + 2) + (0 - 0) = 4
point (1,2) will have sum = (2 + 5) + (2 - 1) = 8
point (2,2) will have sum = (5 + 5) + (2 - 2) = 10


Therefore program should return max(sum) = 10 
I have solved this problem, but I'm struggling to reduce the complexity of the solution to O(n). Is there a more elegant, efficient way to this? 

static int solution(int[] arr) {
    //when array is empty
    if(arr.length == 0) {
        return 0;
    }
    //when array is of length 1
    if(arr.length == 1) {
        return 2*arr[0];
    }
    List&lt;Integer&gt; list1 = new ArrayList&lt;Integer&gt;();
    for(int i=0;i&lt;arr.length;i++) {
        list1.add(arr[i]);
    }
    //copy old list to new one and sort the new one
    List&lt;Integer&gt; list2 = new ArrayList&lt;Integer&gt;(list1);
    Collections.sort(list2);
    //replace values to indexes using 1st list
    for(int i=0;i&lt;list2.size();i++) {
        list2.add(i,list1.indexOf(list2.remove(i)));
    }
    //sort old list. Now my 1st list contains sorted values, and 2nd one       contains corresponding old indexes 
    Collections.sort(list1);
    int i = list1.size()-1;
    //set max to point (n-1,n-1)
    int max = 2*list1.get(i);
    while(i &gt; 0) {
        int j = 1;
        while(j &lt; i) {
            int sum = (list1.get(i) + list1.get(i-j)) + (list2.get(i) -list2.get(i-j));
            if(sum &gt; max) {
                max = sum;
            }
            j++;
        }
        i--;
    }
    return max;
}
I'm not a Lisp guy, but parenthesis are powerful. Change this:

sum = A[i] + A[j] + (j - i)


to that:

sum = (A[i] - i) + (A[j] + j)


Both things are equivalent, but the second one looks quite different.
Its a sum of two numbers and each one only depends on its own index, there's a term based on i and one on j (and the array A of course).

A sum (of independent summands) becomes max, if each summand is max.

The thing is that being independent means that you can calculate both maximums "parallel" to each other while iterating through the array. 
I called them iMax, which is  value - index and jMax which is value + index

Implementation is straight forward:

public class ElementIndexSum
{
    public static void main (String[] args)
    {
        int[] A = {2,3,5};

        int iMax = Integer.MIN_VALUE, jMax = Integer.MIN_VALUE; // minimum possible value serves as neutral starting point to find maximum

        for (int index = 0; index &lt; A.length; ++index)
        {
            // find maximum value from values in array
            iMax = Math.max(iMax, A[index] - index); // with subtraction of its index
            jMax = Math.max(jMax, A[index] + index); // with addition of its index
        }

        System.out.println("maximum( A[i] + A[j] + i - j ) = " + (iMax + jMax));
    }
}


Result in console:

$ java ElementIndexSum 
maximum( A[i] + A[j] + i - j ) = 10


I have no clue about this bick Oh stuff, but if your goal was to iterate only once and not in a nested way, I think the above is what you are looking for.