Определить максимум функции быстрее чем за O(n^2)

#java #алгоритм

Не знаю как нормально оптимизировать алгоритм O(n^2):

 public static long kodyara(long[] arr,long max)
 {
   for (int i = 0; i < arr.length; i++)

         for (int j = 0; j < arr.length; j++) 
         {
             long val = arr[i] * (j+1) + arr[j] * (1 + i);
             max = Math.max(val, max);
         }
     }
  return max;
 }


Дайте совет

Условие задачи (https://algotester.com/en/ArchiveProblem/Display/40366)

Даны:


целочисленный массив A размерности N (1 < N < 100000, 1 < A[i] < 1000)
функция f(i,j) = A[i] * j + A[j] * i


Нужно найти максимальное значение функции.

Примеры:

5 - N

100 1 1 1 1

Max - 501

Ещё пример:

1 - N

1

Max - 2
    

Ответы

Ответ 1

Ограничение на значение элементов массива (1 < A[i] < 1000) сильно упрощает задачу:

Условие

Как уже написал @pavel число может оказаться в максимальной паре только если после
него в последовательности нет бо́льших чисел.

Это легко доказать: если для i и j верно, что i= 0; i--) {
    if (a[i] > max) {
        //записываем максимум
        max = a[i];
        //и индекс
        index[l++] = i;
    }
}

//рассчитываем значения функции для отобранных элементов
int result = -1;
for (int i = 0; i < l; i++) {
    for (int j = i; j < l; j++) {
        int f = (index[i] + 1) * a[index[j]] + (index[j] + 1) * a[index[i]];
        result = max(result, f);
    }
}
return result;


Сложность

Т.о. алгоритм сработает за O(N + L^2), где , где L — длина подпоследовательности
максимальных элементов суффиксов массива. 

Решение кое-как проходит только за счет сильного ограничения на A[i]. Возможно, имеется
универсальный подход с использованием рекуррентных соотношений либо структур данных.


Ответ 2

Ответ был изменён. 

Пусть мы зафиксировали i. Рассмотрим оптимальное j. 

arr[i] * (j+1) + arr[j] * (1 + i) -> max.


Или (помним, i - константа). 

(arr[i]/(i+1)) * (j+1) + arr[j] -> max


Делить на (j+1) нельзя (тогда изменится инвариант максимума).

Если i < i1 и a[i] < a[i1] то элемент i нас вообще не интересует. Таким образом можно
считать что a[i] > a[i+1]. 

Вычислим S[j] для максимального элемента. (который первый из нас интересующих).

Что произойдёт при переходе от i к i+1:
Уменьшится множитель  arr[i]/(i+1) (arr[i+1] - меньше, i+1 - больше). 

По факту S[i+1,j] = S[i,j] - j* [разность множителей].

И нам нужно поддерживать максимум. 
Для этой цели можно использовать любое дерево с интервальной модификацией. В частности
дерево отрезков (можно и Фенвика, но там сложнее писать будет).

Сложность O(N log N). Память O(N) в случе дерева фенвика и O( N log N) при дереве
отрезков.

P.S. желательно обойтись без дробных операций.