Maximize sum-distance for integer array

Question

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 > j

For 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=8

An O(n²) solution is trivial. Is there any O(n) solution (where n is the length of the array)?

Answer 1

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;