C++での回転関数

整数Aの配列を指定し、nを配列Aの長さとします。ここで、Bkを、配列A、kの位置を時計回りに回転させて得られる配列と仮定します。ここで、回転は次のように定義できます-

• F（k）=0 * Bk [0] + 1 * Bk [1] + ... +（n-1）*Bk[n-1]。

ここで、F（0）、F（1）、...、F（n-1）の最大値を見つけます。

したがって、入力が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

最大は26です。

これを解決するには、次の手順に従います-

• n：=配列Aのサイズ。nが0の場合、0を返します

• ret：=0、サイズnの2つの配列を作成します。これらは右と左です

• left [0]：=A [0]

• 1からn–1の範囲のiの場合

  • left [i]：=left [i] + left [i – 1]

  • left [i]：=left [i] + A [i]

• right [n – 1]：=A [n – 1]

• n –1から0までの範囲のiの場合

  • right [i]：=right [i] + right [i + 1]

  • right [i]：=right [i] + A [i]

• rightMul：=0、cnt：=n – 1

• n –1から1までの範囲のiの場合

  • rightMul：=rightMul + A [i] * cnt

  • cntを1減らします

• サイズnの配列xを作成します

• 0からn–2の範囲のiの場合

  • x [i]：=rightMul

  • rightMul：=rightMul – right [i + 1]

• leftMul：=0、cnt：=1

• 0からn–2までの範囲のiの場合

  • leftMul：=leftMul + A [i] * cnt

  • cntを1増やします

• cntを1減らします

• n –1から1までの範囲のiの場合

  • 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