5
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Could you explain further how the points for the array are derived and how the sum is calculated (what is the index)? \$\endgroup\$ – Tunaki Jul 1 '16 at 9:45
  • \$\begingroup\$ "indexes (a,b) where a <= b" ... "sum = a + b + (indexOf(b) - indexOf(a))" - Now, are a and b indexes or values of array elements? \$\endgroup\$ – JimmyB Jul 1 '16 at 9:58
  • \$\begingroup\$ Are you sure O(n) is possible? The number of "points" is (n*n/2) already. \$\endgroup\$ – JimmyB Jul 1 '16 at 10:02
  • \$\begingroup\$ For Array {3,2,5}, point (0,0) will have sum = (3+3) + (0-0). point (0,1) will have sum = (3+2) + (1-0). So basically, ill write it more clearly : sum(i,j)= (A[i] + A[j]) + (j-i). where (i<=j). \$\endgroup\$ – ripudamanrs Jul 1 '16 at 10:20
  • 1
    \$\begingroup\$ Your program incorrectly returns 20 for an input of { 10, 0, 10 } when the correct answer is 22. \$\endgroup\$ – JS1 Jul 1 '16 at 22:44
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Yes, this is exactly the best solution and way of thinking about the problem. \$\endgroup\$ – JS1 Jul 1 '16 at 22:44
  • \$\begingroup\$ This is exactly O(n), as required by OP. Great! +1 \$\endgroup\$ – Tomasz Stanczak Jul 2 '16 at 5:09
  • \$\begingroup\$ Correct me if i am wrong, but this only calculates max values for equal indices like, (0,0),(1,1),(2,2). But for certain problem sets like A[] = {2,-3,4,4} the max value may not lie in (0,0),(1,1),(2,2),(3,3)... (n,n). The solution to this array, and maybe to other cases as well, may lie in indices (i,j) where i != j. \$\endgroup\$ – ripudamanrs Jul 4 '16 at 6:34
  • 1
    \$\begingroup\$ @ripudamanrs each maximum is calculated individually. The call Math.max(iMax, A[index] - index) will return the bigger parameter, based on its value. It does not depend on the outcome of Math.max(jMax, A[index] + index) or if the index is the same. (and vice versa) The suggested solution should find a maximum even if i != j. If in doubt, give it a try. I don't have a compiler at hand at the moment. \$\endgroup\$ – I'll add comments tomorrow Jul 4 '16 at 9:11
  • \$\begingroup\$ oh, i get it now, after debugging your solution provided. that solves my problem, thanks +1. \$\endgroup\$ – ripudamanrs Jul 4 '16 at 10:07
2
\$\begingroup\$

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;
\$\endgroup\$
  • \$\begingroup\$ Thanks, this solution considerably helps in making larger leaps. To think in the direction you have pointed towards, is definitely refreshing. However i'm not able to comprehend the comment you have written next to assigning s to G. \$\endgroup\$ – ripudamanrs Jul 1 '16 at 19:12
  • \$\begingroup\$ Hm, I kind of admire this solution, it tries to make use of clever reasoning which I, being a craftsman and not a scientist, usually don't even try. Still there is one loop there which silently increases complexity: "Go through the array once and find the largest value in A ..." is just a loop from 0 to N. So two loops from 0 to N (N = A.length I guess) plus the inner loop, makes something like O(2* n * x) where (x >= 0 && x <= (n + 1)/2), and that can defeat the advantage of larger leaps. And based on the previous comment increases significantly the mental complexity. \$\endgroup\$ – Tomasz Stanczak Jul 1 '16 at 21:07
  • \$\begingroup\$ I have to go back to school :-( - it will be n + n * x, which has the potential to reach 2 * n. \$\endgroup\$ – Tomasz Stanczak Jul 2 '16 at 5:14
  • 1
    \$\begingroup\$ @ripudamanrs Because the assignment changes G, then you can calculate a new j_start and if j < j_start; j = j_start. \$\endgroup\$ – Emily L. Jul 2 '16 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.