数组中的最大绝对差 [英] Maximum absolute difference in an array
问题描述
我遇到了这个算法问题。我能够实现O（n ^ 2）解决方案。在O（n）时间内有更好的方法吗？
I came across this algorithm question. I was able to implement a O(n^2) solution. Is there a better way of doing this in O(n) time?
问题：
为您提供了N个整数数组， A1，A2，…，AN 。返回所有 1≤i，j≤N 的最大值 f（i，j）。
f（i，j）定义为 | A [i]-A [j] | + | i-j | ，其中 | x | 表示x的绝对值。
You are given an array of N integers, A1, A2 ,…, AN. Return maximum value of f(i, j) for all 1 ≤ i, j ≤ N.
f(i, j) is defined as |A[i] - A[j]| + |i - j|, where |x| denotes absolute value of 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）吗？
Also in my solution the inner loop runs from i + 1 to N, so the worst case is N-1 for that loop. Is my overall solution still O(n^2)?
推荐答案
是的，您的解决方案仍然是 O （N ^ 2）为（N-1）+（N-2）+ ... + 1 = N *（N-1）/ 2 。
Yes, your solution is still O(N^2) as (N - 1) + (N - 2) + ... + 1 = N * (N - 1) / 2.
我将展示如何解决线性时间中的一个更一般的问题：给出二维空间中的点列表（x [i]，y [ i]），找到两个最远的点（相对于曼哈顿距离）。
I'll show how to solve a more general problem in linear time: give a list of points in 2D space (x[i], y[i]), find two farthest points (with respect to Manhattan distance).
-
让我们找到以下几点：max（x [i] + y [i]），max（-x [i] ] + y [i]），max（-y [i] + x [i]）和max（-x [i]-y [i]）在所有i中。
Let's find the following points: max(x[i] + y[i]), max(-x[i] + y[i]), max(-y[i] + x[i]) and max(-x[i] - y[i]) among all i.
让我们计算列表中的每个点与上一步中选择的四个点之间的距离，并选择最大的点。该算法显然考虑了 4 * N 对点，因此可以在线性时间内工作。我声称这是正确的。
Let's compute the distance between every point in the list and the four points chosen during the previous step and pick the largest one. This algorithm clearly works in linear time as it considers 4 * N pairs of points. I claim that it's correct.
为什么？让我们固定一个点（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]的符号）以相同的方式处理。
Why? Let's fix a point (x[k], y[k]) and try to find the farthest one from it. Consider an arbitrary point (x[i], y[i]). Let's expand the absolute value of differences between their coordinates. Let's assume that it's x[i] + x[k] + y[i] + y[k] = (x[k] + y[k]) + x[i] + y[i]. The first term is a constant. If x[i] + y[i] is not maximum among all i, (x[i], y[i]) cannot be the farthest. The three other cases (depending on the sign of x[i] and y[i] in the expansion) are handled in the same manner.
这篇关于数组中的最大绝对差的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
