Max absolute difference of two max values at the different parts of the array?

Question

That's the interview question that I failed back in the days. Nobody of my friends knows where the mistake is and why I've been told that I failed. That's why I decided to ask you to correct my solution Given an array of N integers. An integer K divides array into two subarrays.

  Left part: A[0], A[1]...A[K];
  Right part: A[K+1], A[K+2]... A[N-1];

Need to find the max possible absolute difference of max values in every subarray.

 MaxDiff = Math.Abs(Max(A[0], A[1]...A[K]) - Max(A[K+1], A[K+2]... A[N-1]))
 Example 1: [1, 3, -3]. If K=1, max difference is |3-(-3)| = 6.
 Example 2: [4, 3, 2, 5, 1, 1]. If K=3, max difference is |5 - 1| = 4.

Time and space complexity should be O(n). As I see space complexity of my solution is not O(n) already..

int getMaxDifference(int[]A){
    int [] leftMax = new int [A.length];
    int [] rightMax = new int [A.length];
    int max1 = Integer.MIN_VALUE;
    int max2 = Integer.MIN_VALUE;
    int dif = 0;
    int maxDif = 0;

    for (int i = 0; i< A.length; i++){
        if (A[i]>max1) {max1 = A[i];}
        leftMax[i] = max1;
    }

    for (int j = A.length-1; j>0; j--){
        if (A[j]>max2) {max2 = A[j];}
        rightMax[j] = max2;
    }

    for (int k = 0; k<A.length; k++){
    dif = Math.abs(leftMax[k] - rightMax[k]);
    if (dif>maxDif) {maxDif = dif;}}
    return maxDif;
}

Answer 1

In your program:

leftMax[k] holds the greatest value in A[0],...,A[k].

rightMax[k] holds the greatest value in A[k],...,A[n-1].

However, the right part should start at index k+1, not at k.

Therefore I suggest you change this part:

for (int k = 0; k<A.length; k++){
  dif = Math.abs(leftMax[k] - rightMax[k]);
  if (dif>maxDif) {
    maxDif = dif;
  }
}

to

for (int k = 0; k<A.length - 1; k++){
  dif = Math.abs(leftMax[k] - rightMax[k + 1]);
  if (dif>maxDif) {
    maxDif = dif;
  }
}

In other words, the requirement is to compute:

Math.Abs(Max(A[0], A[1]...A[K]) - Max(A[K+1], A[K+2]... A[N-1]))

but I believe your current program computes:

Math.Abs(Max(A[0], A[1]...A[K]) - Max(A[k], A[K+1], A[K+2]... A[N-1]))

Answer 2

The problem is in the Difference Calculation:
If the Input Array is {4,3,2,5,1,1}
Then the Left Array becomes : {4,4,4,5,5,5}
And the Left Array becomes : {5,5,5,5,1,1}

To Calculate the Difference you should compute the difference at kth index of array leftMAX and (k+1)th index of array rightMax .

i.e. for SubArray {4,3,2,5} consider leftMax's subArray {4,4,4,5} and for SubArray {1,1} consider rightMax's subArray {1,1}

i.e. for SubArray {4,3,2,5} and {1,1} the calculation should be between 3rd Index of leftMax and 4th index of rightMax.

Hence Code becomes

for (int k = 0; k<A.length-1; k++){ dif = Math.abs(leftMax[k] - rightMax[k+1]); if (dif>maxDif) {maxDif = dif;}}

Please note that the rightmost element of leftMax and leftmost element of rightMax doesn't gets included in the calculation.