数组中的最大绝对差异

Question

我遇到了这个算法问题.我能够实现O(n ^ 2)解决方案.在O(n)时间有更好的方法吗？

题:

你得到一个N个整数的数组A1, A2 ,…, AN.返回f(i, j)所有的最大值1 ? i, j ? N. f(i, j)定义为|A[i] - A[j]| + |i - j|,其中|x|表示x的绝对值.

示例:

A=[1, 3, -1]

f(1, 1) = f(2, 2) = f(3, 3) = 0
f(1, 2) = f(2, 1) = |1 - 3| + |1 - 2| = 3
f(1, 3) = f(3, 1) = |1 - (-1)| + |1 - 3| = 4
f(2, 3) = f(3, 2) = |3 - (-1)| + |2 - 3| = 5

所以,我们返回5.

我的答案:

public class Solution {
    public int maxArr(ArrayList<Integer> A) {
        int maxSum = 0;

        for(int i=1; i<=A.size()-1; i++){
            for(int j=i+1; j<=A.size(); j++){
                int tempSum = sum(A.get(i-1), A.get(j-1), i, j);

                if(tempSum > maxSum) {
                    maxSum = tempSum;
                }
            }
        }

        return maxSum;
    }

    public int sum(int Ai, int Aj, int i, int j) {
        return Math.abs(Ai-Aj) + Math.abs(i-j);
    }
}

同样在我的解决方案中,内部循环从i + 1运行到N,因此最坏的情况是该循环的N-1.我的整体解决方案仍然是O(n ^ 2)吗？

Answer 1

是的,您的解决方案仍然O(N^2)如此(N - 1) + (N - 2) + ... + 1 = N * (N - 1) / 2.

我将展示如何在线性时间内解决更一般的问题:给出2D空间中的点列表(x [i],y [i]),找到两个最远点(相对于曼哈顿距离).

1. 让我们找到以下几点:max(x [i] + y [i]),max(-x [i] + y [i]),max(-y [i] + x [i])和max( - x [i] - y [i])在所有i中.

2. 让我们计算列表中每个点与上一步中选择的四个点之间的距离,然后选择最大的点.该算法在考虑4 * N成对点时明显地在线性时间内工作.我声称这是正确的.

3. 为什么？让我们确定一个点(x [k],y [k])并尝试从中找到最远的点.考虑一个任意点(x [i],y [i]).让我们扩展它们坐标之间差异的绝对值.我们假设它是x[i] + x[k] + y[i] + y[k] = (x[k] + y[k]) + x[i] + y[i].第一项是常数.如果x[i] + y[i]不是最大的i,(x[i], y[i])不能是最远的.其他三种情况(取决于扩展中的x [i]和y [i]的符号)以相同的方式处理.

Answer 2

我们肯定可以在这里使用一些数学.尝试扩展您尝试最大化的功能. F(i,j)= | A [i] - A [j] | + | i - j | 扩展它将给我们4个F值.

 1. A[i] - A[j] + i - j   equals to [A[i] + i] - [A[j]+j]
 2. -A[i] + A[j] + i - j  equals to [-A[i] + i] - [-A[j]+j]
 3. A[i] - A[j] + j - i   equals to [A[i] - i] - [A[j]-j]
 4. -A[i] + A[j] + j - i  equals to [-A[i] - i] - [-A[j]-j]

计算向量中所有元素的[A [i] + i],[ - A [i] + i],[A [i] - i],[ - A [i] - i]的最大值和最小值阵列.称之为max1,max2,max3,max4和min1,min2,min3,min4.

你的答案是Max((max1-min1),(max2-min2),(max3-min3),(max4-min4)).

如果有人有兴趣,这是问题链接: - 问题链接

下面是我在c ++中的实现

int Solution::maxArr(vector<int> &A) {
int max1 = INT_MIN,max2 = INT_MIN,max3 = INT_MIN,max4 = INT_MIN,ans = INT_MIN;
int min1 = INT_MAX,min2 = INT_MAX,min3 = INT_MAX,min4 = INT_MAX;
for(int i=0;i<A.size();i++){
    max1 = max(max1,A[i] + i);
    max2 = max(max2,A[i] - i);
    max3 = max(max3,-A[i]+i);
    max4 = max(max4,-A[i]-i);

    min1 = min(min1,A[i] + i);
    min2 = min(min2,A[i] - i);
    min3 = min(min3,-A[i]+i);
    min4 = min(min4,-A[i]-i);

}


    ans = max(ans,max1 - min1);
    ans = max(ans,max2 - min2);
    ans = max(ans,max3 - min3);
    ans = max(ans,max4 - min4);

return ans;

}

Answer 3

如Kraskevich所述,我应用了相同的算法.代码的复杂性是O(4*n)+ O(4*n),因此使总体复杂度为 O(n).

这是代码.

int Solution::maxArr(vector<int> &A) {
int n=A.size(),max1=INT_MIN,max2=INT_MIN,max3=INT_MIN,max4=INT_MIN,ans=INT_MIN;
for(int i=0;i<n;i++){
    max1=max(max1,A[i]+i);
    max2=max(max2,-A[i]+i);
    max3=max(max3,A[i]-i);
    max4=max(max4,-A[i]-i);
}
for(int i=0;i<n;i++){
    ans=max(ans,max1-A[i]-i);
    ans=max(ans,max2+A[i]-i);
    ans=max(ans,max3-A[i]+i);
    ans=max(ans,max4+A[i]+i);
}
return ans;
}