Maximum function value of all rotations of an array

Problem: Given an array of integers arr of length n. Assume RotationK to be an array obtained by rotating the array arr k positions clock-wise, we define a "rotation function" F on arr as follow:

F(k) = 0 * RotationK[0] + 1 * RotationK[1] + ... + (n-1) * RotationK[n-1].

Calculate the maximum value of F(0), F(1), ..., F(n-1).

Example:

Input: arr = [1, 2, 3, 4]
Output: 20
F(0) = (0 * 1) + (1 * 2) + (2 * 3) + (3 * 4) = 0 + 2 + 6 + 12 = 20
F(1) = (0 * 4) + (1 * 1) + (2 * 2) + (3 * 3) = 0 + 1 + 4 + 9 = 14
F(2) = (0 * 3) + (1 * 4) + (2 * 1) + (3 * 2) = 0 + 4 + 2 + 6 = 12
F(3) = (0 * 2) + (1 * 3) + (2 * 4) + (3 * 1) = 0 + 3 + 8 + 3 = 11

So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 20.

Approach: One obvious approach is to generate all the rotations, apply the function F on every rotation and return the maximum of Fs but it will take O(n^2) time. Let's optimize it.

First let's see the different function F values:

F(0) = 0 * arr[0] + 1 * arr[1] + 2 * arr[2] + ... + (n - 1) * arr[n - 1]

F(1) = 1 * arr[0] + 2 * arr[1] + 3 * arr[2] + ... + 0 * arr[n - 1]

F (1) - F(0) = arr[0] + arr[1] + arr[2] + .... - (n - 1) * arr[n - 1]

F(1) - F(0) = arr[0] + arr[1] + arr[2] + ... + arr[n - 1] - arr[n - 1] - (n - 1) * arr[n - 1]

F(1) - F(0) = arr[0] +  arr[1] + arr[2] + ... + arr[n - 1] - n * arr[n - 1]

F (1) - F(0) = SumOfElements - n * arr[n - 1] 

Here SumOfElements = arr[0] + arr[1] + arr[2] + ...  + arr[n - 1] i.e. sum of all the elements of array.

F(1) = F(0) + SumOfElements - n * arr[n - 1]

If you do the same calculation for other rotations, you will find:

F(k) = F(k  - 1) + SumOfElements - n * arr[n - k]

You can prove it using induction too.

Now if you see given the previous rotation's value, we can easily calculate the current rotation's value in constant time. That's all about the explanation of the approach!

Implementation in C#:

        public static int MaxRotateFunction(int[] arr)

        {

            if (arr?.Length == 0)

            {

                return 0;

            }

            int maxF = 0, sumOfElements = 0;

            int n = arr.Length;

            for (int i = 0; i < n; ++i)

            {

                maxF += i * arr[i];

                sumOfElements += arr[i];

            }

            int currF = maxF;

            for (int i = 1; i < n; ++i)

            {

                currF = currF + sumOfElements - n * arr[n - i];

                maxF = Math.Max(maxF, currF);

            }

            return maxF;

        }

Complexity: O(n)