阵列不同部分的两个最大值的最大绝对差值是多少？

Question

那是我在这些日子里失败的面试问题.我朋友中没有人知道错误在哪里以及为什么我被告知我失败了.这就是为什么我决定要求你纠正我的解决方案给定N个整数的数组.整数K将数组分成两个子数组.

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

需要找到每个子阵列中最大可能的最大绝对差值.

 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.

时间和空间复杂度应为O(n).我看到我的解决方案的空间复杂性已经不是O(n)了..

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

在你的程序中：

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

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

然而，正确的部分应该从索引 k+1 开始，而不是从 k 开始。

因此我建议你更改这部分：

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

到

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

换句话说，要求是计算：

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

但我相信你当前的程序计算：

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