The maximum total distance for an integer array

Question

For integer array A, return the maximum possible total distance between the two elements. The total 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] maximum total distance is 24 for i = 0 and j = 8

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

Answer 1

It is possible:

• Create an array and fill it with A [i] + i for each i

• Create another array and fill it with A [j] - j for each j

• Get indexes with highest values ​​i [maxI] and J [maxJ]

• return A [maxI] + A [maxJ] + maxI - maxJ

There you go, O (n)!

Answer 2

For each index, we only need to know one index , which maximizes the sum of A[i] + A[index] + (i - index) = A[i] + i + (A[index] - index) . This means that we need to maintain index , the maximum 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; 

Answer 3

wonderful soln ... pham ... thanks. a more readable soln might be ...

  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 4

// This was the most accurate solution method that passed the test 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;