最大化整数数组的和距离

Question

给定一个整数数组A，返回两个元素之间可能的最大求和距离。对于i，求和距离定义为A[i]A[j]（i-j）

例如，在< code>A = [8，2，4，9，5，8，0，3，8，2]的情况下，i=0且j=8时获得的最大和距离为24

O（n²）解很简单。是否有O（n）解（其中n是数组的长度）？

Answer 1

很好的soln…Pham…谢谢。更具可读性的soln可以是。。。

    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;

Answer 2

这是可能的：

>

创建一个数组，并为每个i填充A[i]i

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

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

返回 A[最大I] A[最大J] 最大I - 最大J

你去吧，哦！！

Answer 3

对于每个索引i，我们只需要知道一个index最大化总和A[i]A[index]（i-index）=A[i]i（A[index]-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;