Программа Javascript для максимальной суммы i*arr[i] среди всех вращений заданного массива

Учитывая массив arr[] из n целых чисел, найдите максимум, который максимизирует сумму значений i*arr[i], где i изменяется от 0 до n-1.

Примеры:

Input: arr[] = {8, 3, 1, 2}
Output: 29
Explanation: Lets look at all the rotations,
{8, 3, 1, 2} = 8*0 + 3*1 + 1*2 + 2*3 = 11
{3, 1, 2, 8} = 3*0 + 1*1 + 2*2 + 8*3 = 29
{1, 2, 8, 3} = 1*0 + 2*1 + 8*2 + 3*3 = 27
{2, 8, 3, 1} = 2*0 + 8*1 + 3*2 + 1*3 = 17

Input: arr[] = {3, 2, 1}
Output: 7
Explanation: Lets look at all the rotations,
{3, 2, 1} = 3*0 + 2*1 + 1*2 = 4
{2, 1, 3} = 2*0 + 1*1 + 3*2 = 7
{1, 3, 2} = 1*0 + 3*1 + 2*2 = 7

Метод 1 : этот метод обсуждает наивное решение , которое занимает O (n ² ) времени.
Решение включает в себя нахождение суммы всех элементов массива в каждом вращении, а затем определение максимального значения суммирования.

• Подход: Простое решение — попробовать все возможные вращения. Вычислить сумму i*arr[i] для каждого вращения и вернуть максимальную сумму.
• Алгоритм:
  1. Поверните массив для всех значений от 0 до n.
  2. Вычислите сумму для каждого вращения.
  3. Проверьте, превышает ли максимальная сумма текущую сумму, а затем обновите максимальную сумму.
• Реализация:

Выход :

29

• Анализ сложности:
  • Сложность по времени: O(n ² ), так как мы используем вложенные циклы.
  • Вспомогательное пространство: O(1), так как мы не используем дополнительное пространство.

Метод 2 : Этот метод обсуждает эффективное решение , которое решает проблему за время O (n). В наивном решении значения рассчитывались для каждого оборота. Поэтому, если это можно сделать за постоянное время, сложность уменьшится.

• Подход: Основной подход заключается в вычислении суммы нового вращения из предыдущих вращений. Это вызывает сходство, когда только множители первого и последнего элементов резко меняются, а множитель каждого другого элемента увеличивается или уменьшается на 1. Таким образом, сумма следующего вращения может быть вычислена из суммы текущего вращения.
• Алгоритм:
  Идея состоит в том, чтобы вычислить значение вращения, используя значения предыдущего вращения. Когда массив поворачивается на единицу, следующие изменения происходят в сумме i*arr[i].
  1. Множитель arr[i-1] меняется с 0 на n-1, т.е. к текущему значению добавляется arr[i-1] * (n-1).
  2. Множители других членов уменьшаются на 1. т.е. (cum_sum – arr[i-1]) вычитается из текущего значения, где cum_sum – сумма всех чисел.

next_val = curr_val - (cum_sum - arr[i-1]) + arr[i-1] * (n-1);

next_val = Value of ∑i*arr[i] after one rotation.
curr_val = Current value of ∑i*arr[i] 
cum_sum = Sum of all array elements, i.e., ∑arr[i].

Lets take example {1, 2, 3}. Current value is 1*0+2*1+3*2
= 8. Shifting it by one will make it {2, 3, 1} and next value
will be 8 - (6 - 1) + 1*2 = 5 which is same as 2*0 + 3*1 + 1*2

• Реализация :

Выход:

29

• Анализ сложности:
  • Временная сложность: O(n).
    Так как требуется один цикл от 0 до n для проверки всех вращений, а сумма текущего вращения вычисляется из предыдущих вращений за время O(1) ).
  • Вспомогательное пространство: O(1).
    Поскольку для этого не требуется дополнительного места, сложность пространства будет O (1)

Метод 3 : метод обсуждает решение с использованием поворота за время O (n). Метод сводки можно использовать только в случае отсортированного или повернутого отсортированного массива. Например: {1, 2, 3, 4} или {2, 3, 4, 1}, {3, 4, 1, 2} и т. д.

• Подход. Предположим, что речь идет об отсортированном массиве. Как мы знаем, для массива максимальная сумма будет, когда массив отсортирован в порядке возрастания. В случае отсортированного повернутого массива мы можем повернуть массив, чтобы сделать его в порядке возрастания. Таким образом, в этом случае необходимо найти опорный элемент, после которого можно будет вычислить максимальную сумму.
• Алгоритм:
  1. Найдите опорную точку массива : если arr[i] > arr[(i+1)%n], то это опорный элемент. (i+1)%n используется для проверки последнего и первого элемента.
  2. После получения опорной точки сумму можно рассчитать, найдя разницу с опорной точкой, которая будет множителем, и умножить ее на текущий элемент при вычислении суммы.
• Реализации:

Выход:

29

• Анализ сложности:
  • Временная сложность: O(n)
    Поскольку для перехода от 0 к n, чтобы найти точку опоры, требовался только один цикл. Чтобы найти сумму, потребовался еще один цикл, поэтому сложность остается O(n) .
  • Вспомогательное пространство: O(1).
    Нам не требуется дополнительное пространство, поэтому вспомогательное пространство составляет O (1)