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.
給定整數(shù)數(shù)組A以及其長(zhǎng)度n洪橘。
假設(shè)數(shù)組Bk是由數(shù)組A順時(shí)針旋轉(zhuǎn)k個(gè)位置（循環(huán)右移k位）所得鲸睛，將旋轉(zhuǎn)函數(shù)F定義如下：
F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].
計(jì)算F(0), F(1), ..., F(n-1)中的最大值洛巢。
注：給定的n將小于10^5
思路
【錯(cuò)誤】開始時(shí)考慮直接將每一次輪轉(zhuǎn)函數(shù)的值計(jì)算出來(lái)，進(jìn)行比較厦滤，提交時(shí)發(fā)現(xiàn)超時(shí)錯(cuò)誤援岩，回顧題目時(shí)發(fā)現(xiàn)未注意到題目中關(guān)于n的大小的要求。由于題目中n的值將會(huì)到達(dá)105掏导，將每一次的值都進(jìn)行計(jì)算將使時(shí)間復(fù)雜度升至O(n2)
【時(shí)間復(fù)雜度O(n)的做法】利用F(k)和F(k+1)的關(guān)系
由于每一次循環(huán)迭代都是循環(huán)右移一位操作享怀，根據(jù)F的表達(dá)式可得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;
}
};
