C++で配列の回転のみを許可してSum(i*arr[i])の最大値を求めるアルゴリズム

問題概要

この問題では、n個の要素からなる配列arr[]が与えられます。配列に対しては回転操作のみが許可されており、その条件下でSum(i*arr[i])の最大値を求める必要があります。最大の合計値を見つけるために、回転は何度行っても構いません。

例を使って問題を理解しましょう。

入力

arr[] = {4, 1, 3, 7, 2}

出力

43

説明

配列を1回回転すると {2, 4, 1, 3, 7} となり、このとき最大値が得られます。

Sum = 0*2 + 1*4 + 2*1 + 3*3 + 4*7 = 0 + 4 + 2 + 9 + 28 = 43

解法アプローチ

最も単純な解法は、配列をn回回転させ、各回転後にsum(i*arr[i])を計算して、その中の最大値を返す方法です。しかしこの方法の時間計算量はO(n²)となり、非効率です。

より効率的な解法は、数式を利用することです。回転なしの状態でのsum(i*arr[i])の値から、各回転後の値を漸化的に導き出すことで、全体をO(n)で処理できます。

それでは、数式的に式を導出してみましょう。

k回目の回転後の合計をsum(k)とする。
sum(0) = 0*arr[0] + 1*arr[1] + ... + (n-1)*arr[n-1] => 式1

ここで配列を1回回転すると、合計は次のように変化します。

sum(1) = 0*arr[n-1] + 1*arr[0] + ... + (n-1)*arr[n-2] => 式2

式2 − 式1 を計算すると:
sum(1) − sum(0) = arr[0] + arr[1] + … + arr[n-2] − (n−1)*arr[n-1]

同様に、sum(2) − sum(1)は以下のようになります。

sum(2) − sum(1) = arr[0] + arr[1] + …. + arr[n-3] − (n−1)*arr[n-2] + arr[n-1]

これらの関係を一般化すると、次の重要な式が得られます。

sum(k) − sum(k-1) = arr[0] + arr[1] + …. + arr[n-1] − n*arr[n-k]

この式を使えば、初期値であるsum(0)さえ分かれば、任意の回転回数kにおけるsum(k)の値を定数時間で求められます。

実際の解法では、まず配列の全要素の合計(arrSum)とsum(0)(currSum)を一度のループで計算します。その後、ループを使ってk=1からn-1までの各sum(k)の値を順に更新し、その中の最大値を記録していきます。最終的に得られた最大値を返します。

このソリューションの動作を示すプログラム:

例

#include <iostream>
using namespace std;
int findMaxSumRotation(int arr[], int n){
    int arrSum = 0;
    int currSum = 0;
    for (int i=0; i<n; i++){
        arrSum = arrSum + arr[i];
        currSum = currSum+(i*arr[i]);
    }
    int maxSum = currSum;
    for (int j=1; j<n; j++){
        currSum = currSum + arrSum-n*arr[n-j];
        if (currSum > maxSum)
            maxSum = currSum;
    }
    return maxSum;
}
int main(){
    int arr[] = {4, 1, 3, 7, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"The maximum value of sum(i*arr[i]) using rotations is "<<findMaxSumRotation(arr, n);
    return 0;
}

出力

The maximum value of sum(i*arr[i]) using rotations is 43

まとめ

この手法により、全回転パターンを毎回再計算するO(n²)の素朴なアプローチと比べ、前回の合計値との差分を利用した漸化式によって、わずか2回の線形走査で答えを求めることができます。空間計算量もO(1)に抑えられるため、大規模な配列に対しても効率的に動作します。