我遇到了这个算法问题。我能够实现 O(n^2) 解决方案。在 O(n) 时间内有更好的方法吗?
问题:
给定一个包含 N 个整数的数组,A1, A2,..., AN
。对于所有 1 ≤ i, j ≤ N
,返回 f(i, j)
的最大值。
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)?
最佳答案
是的,您的解决方案仍然是 O(N^2)
作为 (N - 1) + (N - 2) + ... + 1 = N * (N - 1 )/2
。
我将展示如何在线性时间内解决更一般的问题:给出二维空间中的点列表 (x[i], y[i]),找到两个最远的点(相对于曼哈顿距离)。
让我们找到以下点:max(x[i] + y[i]), max(-x[i] + y[i]), max(-y[i] + x[i ]) 和 max(-x[i] - y[i]) 在所有 i 中。
让我们计算列表中每个点与上一步中选择的四个点之间的距离,并选择最大的一个。该算法在考虑
4 * N
点对时显然可以在线性时间内运行。我声称这是正确的。为什么?让我们固定一个点 (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] 的符号)以相同方式处理。
关于algorithm - 数组中的最大绝对差,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40272649/