Find maximum value of Point represented by an Array of values for each coordinate

Question

Suppose there is an array A = {3,2,5}, then points for this array correspond to indexes (i,j) where i <= 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<Integer> list1 = new ArrayList<Integer>();
    for(int i=0;i<arr.length;i++) {
        list1.add(arr[i]);
    }
    //copy old list to new one and sort the new one
    List<Integer> list2 = new ArrayList<Integer>(list1);
    Collections.sort(list2);
    //replace values to indexes using 1st list
    for(int i=0;i<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 > 0) {
        int j = 1;
        while(j < i) {
            int sum = (list1.get(i) + list1.get(i-j)) + (list2.get(i) -list2.get(i-j));
            if(sum > max) {
                max = sum;
            }
            j++;
        }
        i--;
    }
    return max;
}

Answer 1

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.

Answer 2

I'm not sure that linear time is possible for the problem as you have described it. It is, see accepted answer.

I have a way to make it faster though:

Go through the array once and find the largest value in \$A\$, label it \$A_p\$ . Make sure you keep track of the largest and smallest \$p\$ if there are duplicate values. Then let $$G^* = 2A_p+ p_{max} - p_{min}$$.

This is our greedy guess at the maximum sum that we will use as a starting point.

Next we want to find a lower bound on \$j\$ to limit our search space for any given \$i\$: $$A_i+A_j+j-i > G^* \Leftrightarrow j > G^* +i-A_i-A_j$$

Unfortunately we can't have \$A_j\$ in the calculation of the bound of \$j\$ as that wouldn't be possible to compute. But note that if we replace \$A_j\$ with \$A_p\$ which is at least as large, then we will only lower the bound on \$j\$ and we will not miss any solutions.

At this point we can start scanning of \$A\$ and update \$G^*\$ as we go to have higher and higher lower bounds on \$j\$ as we go.

Technically this is still \$O(n^2)\$ but with a smaller constant as you are able progressively take larger and larger skips.

Pseudocode:

int G = A_p*2 + p_max - p_min;
for(int i = 0; i < N; ++i){
    int j_start = max(i, G + i - A_p -A[i]);
    for(int j = j_start; j < N; ++j){
        int s = A[i] + A[j] + j - i;
        if( s > G){
            G = s; // You could check if you can skip ahead on J here.
        }
    }
}
return G;