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



• 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 list1 = new ArrayList();
    for(int i=0;i list2 = new ArrayList(list1);
    Collections.sort(list2);
    //replace values to indexes using 1st list
    for(int i=0;i 0) {
        int j = 1;
        while(j  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 < 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.

StackExchange Code Review Q#133583, answer score: 7