C ++中的旋转函数
假设我们给定了一个整数数组A，并且n是数组A的长度。现在假设Bk是通过旋转数组A获得的数组，k顺时针旋转。在这里旋转可以定义为-
F(k)=0*Bk[0]+1*Bk[1]+...+(n-1)*Bk[n-1]。
现在找到F，F(1)，...，F(n-1)的最大值。
因此，如果输入类似于A=[4,3,2,6]，则-
F=（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
最大值为26。
为了解决这个问题，我们将遵循以下步骤-
n：=数组A的大小，如果n为0，则返回0
ret：=0，创建两个大小为n的数组，它们分别是左右
左[0]：=A[0]
当我在1到n–1的范围内时
left[i]：=left[i]+left[i–1]
左[i]：=左[i]+A[i]
右[n–1]：=A[n–1]
当我在n–1范围内下降到0
right[i]：=right[i]+right[i+1]
right[i]：=right[i]+A[i]
rightMul：=0，cnt：=n–1
因为我的范围是n–1到1
rightMul：=rightMul+A[i]*cnt
减少cnt1
制作大小为n的数组x
对于i，范围为0到n–2
x[i]：=rightMul
rightMul：=rightMul–右[i+1]
leftMul：=0，cnt：=1
对于范围从0到n–2的i
leftMul：=leftMul+A[i]*cnt
增加cnt1
减少cnt1
因为我的范围是n–1到1
x[i]：=x[i]+leftMul
leftMul：=leftMul–A[i–1]*cnt
如果i–2>=0，则leftMul：=leftMul+left[i–2]
返回x的最大值
范例（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int maxRotateFunction(vector<int>& A) {
lli n = A.size();
if(n == 0) return 0;
lli ret = 0;
vector <lli>right(n);
vector <lli> left(n);
left[0] = A[0];
for(lli i = 1; i < n; i++){
left[i] += left[i - 1];
left[i] += A[i];
}
right[n - 1] = A[n - 1];
for(lli i = n - 2; i >= 0; i--){
right[i] += right[i + 1];
right[i] += A[i];
}
lli rightMul = 0;
lli cnt = n - 1;
for(lli i = n - 1; i > 0; i--){
rightMul += (A[i] * cnt);
cnt--;
}
vector <lli> x(n);
for(lli i = 0; i < n - 1; i++){
x[i] = rightMul;
rightMul -= right[i + 1];
}
lli leftMul = 0;
cnt = 1;
for(lli i = 0; i < n - 1; i++){
leftMul += A[i] * cnt;
cnt++;
}
cnt--;
for(lli i = n - 1; i >= 1; i--){
x[i] += leftMul;
leftMul -= (A[i - 1] * cnt);
if(i - 2 >= 0) leftMul += left[i - 2];
}
ret = INT_MIN;
for(lli i = 0; i < x.size(); i++) ret = max(ret, x[i]);
return ret;
}
};
main(){
Solution ob;
vector<int> v = {4,3,2,6};
cout <<(ob.maxRotateFunction(v));
}输入值
[4,3,2,6]
输出结果
26