Given an array of integers A and let n to be its length.
Assume Bk to be an array obtained by rotating the array Ak positions clock-wise, we define a "rotation function" F on A as follow:
F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].
Calculate the maximum value of F(0), F(1), ..., F(n-1).
Note:
n is guaranteed to be less than 105.
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.
给定整数数组A以及其长度n。
假设数组Bk是由数组A顺时针旋转k个位置（循环右移k位）所得，将旋转函数F定义如下：
F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].
计算F(0), F(1), ..., F(n-1)中的最大值。
注：给定的n将小于10^5
思路
【错误】开始时考虑直接将每一次轮转函数的值计算出来，进行比较，提交时发现超时错误，回顾题目时发现未注意到题目中关于n的大小的要求。由于题目中n的值将会到达105，将每一次的值都进行计算将使时间复杂度升至O(n2)
【时间复杂度O(n)的做法】利用F(k)和F(k+1)的关系
由于每一次循环迭代都是循环右移一位操作，根据F的表达式可得F(k+1)=F(k)+sum-n*B[n-1]
class Solution {
public:
int maxRotateFunction(vector<int>& A) {
long long res=0;
long long sum=0;
long long n=A.size();
for(auto it=A.begin();it!=A.end();it++){
sum+=*it;
}
long long pre=0;
long long cur=0;
for(int i=0;i<n;i++){
pre+=i*A[i];
}
res=pre;
for(int i=1;i<n;i++){
cur=pre+sum-n*A[n-i];
res=(res<cur)?cur:res;
pre=cur;
}
return res;
}
};
