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

• 减少cnt 1

• 制作大小为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

• 增加cnt 1

• 减少cnt 1

• 因为我的范围是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