# Java O(n) solution with explanation

• ``````F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]
F(k-1) = 0 * Bk-1[0] + 1 * Bk-1[1] + ... + (n-1) * Bk-1[n-1]
= 0 * Bk[1] + 1 * Bk[2] + ... + (n-2) * Bk[n-1] + (n-1) * Bk[0]
``````

Then,

``````F(k) - F(k-1) = Bk[1] + Bk[2] + ... + Bk[n-1] + (1-n)Bk[0]
= (Bk[0] + ... + Bk[n-1]) - nBk[0]
= sum - nBk[0]
``````

Thus,

``````F(k) = F(k-1) + sum - nBk[0]
``````

What is Bk[0]?

``````k = 0; B[0] = A[0];
k = 1; B[0] = A[len-1];
k = 2; B[0] = A[len-2];
...
``````
``````int allSum = 0;
int len = A.length;
int F = 0;
for (int i = 0; i < len; i++) {
F += i * A[i];
allSum += A[i];
}
int max = F;
for (int i = len - 1; i >= 1; i--) {
F = F + allSum - len * A[i];
max = Math.max(F, max);
}
return max;
``````

• Explanation:
F(k) = 0 * Bk[0-k] + 1 * Bk[1-k] + ... + (n-1) * Bk[n-1-k]
F(k+1) = 0 * Bk[n-(k+1)] + 1 * Bk[1-(k+1)] + ... + (n-2) * Bk[n-1-(k+1)]
= 0 * Bk[n- 1 - k] + 1 * Bk[0-k] + ... + (n-2) * Bk[n-2-k]
= 0 * Bk[0-k] + 1 * Bk[1-k] + ... + (n-1) * Bk[n-1-k] + sum - n *Bk[n-(k+1)]
Note: Bk[n- 1 - k] == Bk[n-(k+1)]
Then,

``````F(k+1) - F(k) = Bk[0-k] + Bk[1-k] + ... + Bk[n-2-k] - (n-1)Bk[n-(k+1)]
= (Bk[0] + ... + Bk[n-1]) - n*Bk[n-(k+1)]
= sum - n*Bk[n-(k+1)]

Thus,

F(k) = F(k-1) + sum - n* Bk[n-k]``````

• Thanks for the post. It is really a beautiful solution.

However, I think the above deductions may have some flaws. Because we cannot get the `F(0)` from `F(k)`. Personally I would use only
the base case, `k = 0`

``````F(0) = 0 * Bk[0] + 1 * Bk[1] + ... + (n - 1) * Bk[n - 1]
``````

and the case when `k > 0 and k < n`

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

For those who got confused why we will start from `i = len - 1`:

``````F(1) = F(0) + sum - n * A[n - 1], here n = len so that A[n - 1] == A[i]
F(2) = F(1) + sum - n * A[n - 2]
...
F(k) = F(k - 1) + sum - n * A[n - k]
``````

Why we will end if `i < 1`? It's because we deduced `k < n` and `k > 0`. So that it's obvious`n - k > 0`, which means `i > 0`.

Hope this will help a little bit to understand this nice post.

• @Free9
No need start from i = len - 1 and it will confuse some other ppl.
Thus, we should start with k = 1 till k = len -1.

See my Explanation:
F(k) = 0 * Bk[0-k] + 1 * Bk[1-k] + ... + (n-1) * Bk[n-1-k]
F(k+1) = 0 * Bk[n-(k+1)] + 1 * Bk[1-(k+1)] + ... + (n-2) * Bk[n-1-(k+1)]
= 0 * Bk[n- 1 - k] + 1 * Bk[0-k] + ... + (n-2) * Bk[n-2-k]
= 0 * Bk[0-k] + 1 * Bk[1-k] + ... + (n-1) * Bk[n-1-k] + sum - n *Bk[n-(k+1)]

Note: Bk[n- 1 - k] == Bk[n-(k+1)]
Then,

F(k+1) - F(k) = Bk[0-k] + Bk[1-k] + ... + Bk[n-2-k] - (n-1)Bk[n-(k+1)]
= (Bk[0] + ... + Bk[n-1]) - nBk[n-(k+1)]
= sum - n
Bk[n-(k+1)]

Thus,

F(k) = F(k-1) + sum - n* Bk[n-k]

Code change a little bit:
int allSum = 0;
int len = A.length;
int F = 0;
for (int i = 0; i < len; i++) {
F += i * A[i];
allSum += A[i];
}
int max = F;
for (int k = 1; k < len; k++) {
F = F + allSum - len * A[len - k];
max = Math.max(F, max);
}
return max;

• Great solution. Two critical paths:

• The relationship between F(k) and F(k-1), build the DP function
``````F(k) = F(k-1) + sum - n * Bk[0]
``````
• The relationship bettwen Bk[0] with A[i]

Thanks!

• came up with the same solution with c#,

``````public class Solution {
public int MaxRotateFunction(int[] A) {
if (A == null) {
return 0;
}

int current = 0;
int sum = 0;

for(int i = 0; i < A.Length; i++) {
current += i * A[i];
sum += A[i];
}

int max = current;

for(int i = A.Length - 1; i >= 1; i--) {
current = current + sum - A.Length * A[i];
max = Math.Max(max, current);
}

return max;
}
}
``````

• This post is deleted!

• What the means of rotating the array A k positions clock-wise

• Thanks For sharing!!!

``````public class Solution {
public int maxRotateFunction(int[] A) {
if(A==null||A.length<1) return 0;

int sum=0;
int t_pre=0;
for(int i=0;i<A.length;i++){
sum+=A[i];
t_pre+=i*A[i];
}

int max=t_pre;
for(int i=A.length-1;i>=1;i--){
int current=t_pre+sum-A.length*A[i];
max=Math.max(max,current);
t_pre=current;
}
return max;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.