最大化整数数组的总距离

Question

给定一个整数数组A，返回两个元素间可能的最大和距离。其中，和距离定义为A[i] + A[j] + (i - j)（其中i > j）。

例如，对于A = [8, 2, 4, 9, 5, 8, 0, 3, 8, 2]，最大和距离为24，当i=0，j=8时实现。

O(n²)的解法很显然。是否有O(n)的解法（其中n是数组的长度）？

- jondoe

---

当然，可以使用以下代码来计算：max(A[i] + i for i in range(len(A)) + max(A[j] - j for j in range(len(A)))。然后我会看你是否添加了绝对值或限制条件 i < j，接着我会去查找重复项。 - David Eisenstat

@DavidEisenstat 这真的有区别吗？ 如果 i - j 为负数，则似乎存在使用 i 和 j 交换的更好解决方案。 在这种情况下，如果不费太多力气找到一个解决方案，我认为我们仍然可以将其标记为重复项。 - Niklas B.

@NiklasB。之前有人问过但没有回答：http://stackoverflow.com/questions/31139032/in-an-array-find-the-largest-sum-distance-between-any-2-elements 。我会将那个问题关闭并转移到这里。 - David Eisenstat

@NiklasB。还有另一个版本，目标不太容易分离——也许是A[i] + A[j] - |i - j|。我记得回答过那个问题。 - David Eisenstat

问题如果有一个例子会更清晰。请问您能分享一个例子吗？ - Colonel Panic

@NiklasB。i > j 可以产生差异，因为它禁止了 i == j，因此我们无法独立优化 f(i) 和 h(j)。 - piotrek

Answer 1

对于每个索引i，我们只需要知道一个索引，它最大化了总和A[i] + A[index] + (i - index) = A[i] + i + (A[index] - index)。也就是说，我们只需要维护一个索引，使得A[index] - index最大。

int index = 0;
int result = 0;

for(int i = 1; i < n; i++){
    int total = A[i] + i + A[index] - index;
    result = max(result, total);
    if(A[i] - i > A[index] - index){
        index = i;
    }
}
return result;

- Pham Trung

---

考虑解决方案时，无法认真考虑将两个巨大的数组存储起来比跟踪一个整数更好的方案。 - Stef

@Stef 这取决于使用情况。无论如何，它们基本上是相同的方法，其中一个更适用于数量级为10^6的大型数组，另一个更易于调试。由于他没有提到必须遍历大型数组，所以我写了易于调试的版本。 - xXliolauXx

@xXliolauXx 拥有一个额外的数组并不意味着能更好地进行调试。 - Pham Trung

我没有给你的代码投反对票，但是你的代码假设结果至少为0——我在问题规格中没有看到这一点。 - Stef

Answer 2

有可能这样做：

• 创建一个数组，并用A[i]+i来填充每个i

• 创建另一个数组，并用A[j]-j来填充每个j

• 获取具有最高I[maxI]和J[maxJ]的索引

• 返回A[maxI]+A[maxJ]+maxI-maxJ

这就是O(n)的做法！

- xXliolauXx

---

你能详细说明倒数第二步骤吗？ - Sumeet

无需创建新数组 FWIW - Niklas B.

这个解决方案有两个主要问题，首先，当它只需要两个索引maxI和maxJ时，你需要两个数组来存储不必要的数据，其次，当maxJ> maxI时，这个解决方案将给出错误的答案，因此对于一对（maxI，maxJ）的答案应该是A[maxI] + A[maxJ] + maxJ - maxI。而且它无法处理maxI = maxJ的情况。 - Pham Trung

第三，你能演示一下这个解决方案如何更好地进行调试吗？ - Pham Trung

好吧，给你一分，因为楼主要求两个元素...不过是的，它更易于调试，因为你可以查看他用来计算东西的实际数组。无论如何，你得到了我的赞同，因为你的代码似乎完全没问题（除了Stef的建议）。 - xXliolauXx

Answer 3

很棒的解决方案...Pham...谢谢你。 更易读的解决方案可能是...

    int sumP = Integer.MIN_VALUE;
    int sumQ = Integer.MIN_VALUE;
    for(int i = 0; i < A.length; i++){
        sumP = Math.max(A[i] - i, sumP);
        sumQ = Math.max(A[i] + i, sumQ);
    }
    return sumP + sumQ;

- Sheikh Mohammed Habib

---

优秀的回答，您能否详细解释一下？ - Roni Gadot

Answer 4

这是经过100%测试的最准确的解决方法。

var sumP = MIN_VALUE*2;
var sumQ = MIN_VALUE*2;
for(var i = 0; i < A.length; i++){
    sumP = Math.max(A[i] - i, sumP);
    sumQ = Math.max(A[i] + i, sumQ);
}
return sumP + sumQ;

- software appdev

---

很抱歉，当我编辑时，我没有注意到它是JavaScript。我在想Java。而且无法编辑回来，因为它声称“编辑必须超过6个字符。”所以请将其恢复到您拥有的版本。再次抱歉。 - WesternGun