Учитывая массив A размера n, содержащий неотрицательные целые числа, вернуть максимально возможное суммарное расстояние между двумя элементами. Суммарное расстояние определяется как:
int length= A[i] +A[j];
if(abs(j-i)<=n-abs(j-i))
length+=n-abs(j-i);
else
length+=abs(j-i);
Например, при A = [8, 2, 4, 9, 5, 8, 0, 3, 7, 2], максимальное суммарное расстояние равно 24 = (8 + 9 + 7) достигается при i = 0 и j = 3
Решение O (n²) тривиально. Есть ли какое-либо решение O (n) или O (nlogn)?
Любые предложения, подходы или псевдокод будут очень полезны.