396. Rotate Function

Level - medium

Task

You are given an integer array nums of length n.

Assume arrk to be an array obtained by rotating nums by k positions clock-wise. We define the rotation function F on nums as follow:

F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]. Return the maximum value of F(0), F(1), ..., F(n-1).

The test cases are generated so that the answer fits in a 32-bit integer.

Объяснение

Дан массив целых чисел A. Требуется найти максимальное значение функции F(k), которая определяется следующим образом: F(k)=0⋅A[0]+1⋅A[1]+2⋅A[2]+…+(n−1)⋅A[n−1] где k — это количество поворотов массива. Поворот массива на k позиций означает, что каждый элемент сдвигается на k позиций вправо, и элементы, которые выходят за пределы массива, перемещаются в начало.

Пример Рассмотрим массив A = [4, 3, 2, 6]. Без поворота (k = 0): F(0)=0⋅4+1⋅3+2⋅2+3⋅6=0+3+4+18=25 Поворот на 1 позицию (k = 1): A=[6,4,3,2], F(1)=0⋅6+1⋅4+2⋅3+3⋅2=0+4+6+6=16 Поворот на 2 позиции (k = 2): A=[2,6,4,3], F(2)=0⋅2+1⋅6+2⋅4+3⋅3=0+6+8+9=23 Поворот на 3 позиции (k = 3): A=[3,2,6,4], F(3)=0⋅3+1⋅2+2⋅6+3⋅4=0+2+12+12=26 Максимальное значение функции F(k) для данного массива равно 26.

Задача Требуется написать алгоритм, который находит максимальное значение функции F(k) для заданного массива A.

Возможное решение Один из подходов к решению этой задачи — вычислить значения F(k) для всех возможных поворотов и найти максимальное из них. Однако этот подход может быть неэффективным для больших массивов. Более оптимальный способ заключается в использовании формулы для вычисления F(k) на основе предыдущего значения F(k-1), что позволяет снизить сложность алгоритма.

Example 1:

Input: nums = [4,3,2,6]
Output: 26
Explanation:
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

Example 2:

Input: nums = [100]
Output: 0

Constraints:

n == nums.length
1 <= n <= 10^5
-100 <= nums[i] <= 100