Given an array of integers `A`

and let *n* to be its length.

Assume `B`

to be an array obtained by rotating the array _{k}`A`

*k* positions clock-wise, we define a “rotation function” `F`

on `A`

as follow:

`F(k) = 0 * B`

._{k}[0] + 1 * B_{k}[1] + ... + (n-1) * B_{k}[n-1]

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

.

**Note:***n* is guaranteed to be less than 10^{5}.

**Example:**

A = [4, 3, 2, 6] 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.

## Solution

To me it is easier to see the solution if you leave the array as is and rotate the factors left (same result as rotating array right).

For simplicity take an array with 4 elements

[a,b,c,d]

f(0) = 0a + 1b + 2c +3d

f(1) = 3a + 0b + 1c +2d

f(2) = 2a + 3b + 0c +1d

f(3) = 1a + 2b + 3c +0d

Now look what happens when you take difference between f(k) – f(k-1)

f(1) – f(0) = 3a – b – c – d = 4a – (a + b + c + d) = length * a – sum

f(2) – f(1) = -a + 3b – c – d = 4b – (a + b + c + d) = length * b – sum

f(3) – f(2) = -a – b +3c – d = 4c – (a + b + c + d) = length * c – sum

You can see if you calculate (manually) f(0) you can get f(1) by adding length * a and subtracting the sum.

So initially you need to compute the sum and f(0) then just iterate through and get the value of f(i) for each i and record the max.

Hope that helps!

**Program**

class Solution { public int maxRotateFunction(int[] A) { int sumA = 0; int prevRotationSum = 0; for(int i=0;i<A.length;i++) { sumA += A[i]; prevRotationSum += i*A[i]; } int len = A.length; int max = prevRotationSum; for(int i=A.length-1;i>0;i--) { prevRotationSum = prevRotationSum + sumA - len * A[i]; max = Math.max(max,prevRotationSum); } return max; } }

**Code Walkthrough**

```
A = [4, 3, 2, 6]
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.
for (int i = 0; i < A.length; i++) {
sumA += A[i];
prevRotationSum += i * A[i];
}
sumA = 15;
prevRotationSum = 25;
A = [4, 3, 2, 6]
int len = A.Length; //4
for(int i=len-1;i>0;i--)
{
//i runs from 3, 2, 1
//i = 3
prevRotationSum = prevRotationSum + sumA - len * A[i];
prevRotationSum = 25 + 15 - 4 * 6 = 40 - 24 = 16;
//i = 2
prevRotationSum = prevRotationSum + sumA - len * A[i];
prevRotationSum = 16 + 15 - 4 * 2 = 23
//i = 1
prevRotationSum = prevRotationSum + sumA - len * A[i];
prevRotationSum = 23 + 15 - 4 * 3 = 26
}
```