# C++ 9ms Solution With Concise Explanation

• The idea is very simple. We only calculate the difference between two iterations. Try to write in math expression as below:
`F(k) = F(k - 1) + ( sum(A) - A.size() * A(the last element in A after rotate k - 1 positions.))`

Let's take an example . `A = [4, 3, 2, 6]`

First, calculate `sum(A) = 4 + 3 + 2 + 6 =15`

And `F[0] = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25`

Then we begin to rotate. `F[1] = F[0] + (sum(A) - A.size() * 6) = 25 + (15 - 4 * 6) = 16`

And `F[2] = F[1] + (sum(A) - A.size() * 2) = 16 + (15 - 8) = 23` (`2`is the last element of A after rotate A for k - 1 = 1 position)

Since we can calculate `sum, F[0]` in O(n) time. And then we get `F[k]`from `F[k - 1`using O(1) time, the total time complexity is O(n).

Here is my AC code. Hope it helps.

``````class Solution {
public:
int maxRotateFunction(vector<int>& A) {
if (A.size() == 0) return 0;
int sum = 0, current = 0;
for(int i = 0; i < A.size(); ++i) {
sum+= A[i];
current+= i * A[i];
}
int maximum = INT_MIN;
for (int i = A.size() - 1; i >=0; --i) {
current+= sum - A.size() * A[i];
maximum = max(maximum, current);
}
return maximum;
}
};
``````

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