algorithm - Maximize sum-distance for integer array - Stack Overflow
Given an integer array A, return the maximum possible sum-distance between two elements. The sum-distance is defined as
For example with
An O(n2) solution is trivial. Is there any O(n) solution (where n is the length of the array)?
Given an integer array A, return the maximum possible sum-distance between two elements. The sum-distance is defined as
A[i] + A[j] + (i - j)
for i > jFor example with
A = [8, 2, 4, 9, 5, 8, 0, 3, 8, 2]
the max sum-distance is 24 achieved with i=0 and j=8An O(n2) solution is trivial. Is there any O(n) solution (where n is the length of the array)?
For each index i, we only need to know one
index
that maximize the sum A[i] + A[index] + (i - index) = A[i] + i + (A[index] - index)
. Which mean, we only need to maintain an index
, which A[index] - index
is maximum.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;
Read full article from algorithm - Maximize sum-distance for integer array - Stack Overflow