C++で配列の全回転における i*arr[i] の最大合計を求める方法

問題概要

この問題では、整数配列 arr が与えられます。求めるのは、配列のすべての回転（ローテーション）の中で、各要素にそのインデックスを掛けた値の合計 i * arr[i] が最大になる値です。

具体例で理解する

入力: arr = {4, 8, 1, 5}
出力: 37

解説: すべての回転と、それぞれの i*arr[i] の合計は以下の通りです。

すべての回転と i*arr[i] の合計:
{4, 8, 1, 5} = 4*0 + 8*1 + 1*2 + 5*3 = 25
{8, 1, 5, 4} = 8*0 + 1*1 + 5*2 + 4*3 = 23
{1, 5, 4, 8} = 1*0 + 5*1 + 4*2 + 8*3 = 37
{5, 4, 8, 1} = 5*0 + 4*1 + 8*2 + 1*3 = 23
最大値 37 は3番目の回転で得られます。

解法1: 全回転を試す単純なアプローチ（O(n²)）

最もシンプルな方法は、各回転ごとに「要素 × インデックス」の合計をすべて計算し直し、その中から最大値を記録することです。具体的には、配列を n 回回転させながら各合計を求め、現在の合計がこれまでの最大値（maxSum）を上回ったら更新していきます。

実装例

#include<iostream>
using namespace std;

int findMax(int a, int b){
    if(a > b)
        return a;
    return b;
}

int calculateMaxSum(int arr[], int n){
    int maxSum = 0, sum = 0;
    for (int i = 0; i < n; i++){
        sum = 0;
        for (int j = 0; j < n; j++){
            int index = (i + j) % n;
            sum += j * arr[index];
        }
        maxSum = findMax(maxSum, sum);
    }
    return maxSum;
}

int main(){
    int arr[] = {4, 8, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum sum of all the rotation of the array is " << calculateMaxSum(arr, n);
    return 0;
}

出力

The maximum sum of all the rotation of the array is 37

この方法は直感的で分かりやすいものの、二重ループを使用するため計算量は O(n²) となり、配列のサイズが大きくなると処理時間が増大します。

解法2: 前回の合計を利用する効率的なアプローチ（O(n)）

より効率的な方法は、直前の回転の合計値を利用して次の回転の合計を求めることです。回転によって合計値がどう変化するかを観察すると、次の漸化式が成り立ちます。

nextSum = currentSum - (arraySum - arr[i-1]) + arr[i-1] * (n-1)

この式の意味は以下の通りです。

• 回転によって、先頭以外のすべての要素のインデックスが1つずつ減るため、合計から配列全体の合計（arraySum）を引きます。
• ただし、直前の回転の先頭にあった要素 arr[i-1] は末尾に移動し、インデックスが n-1 になるため、その分を加算し直します。

この式を使って nextSum を順次求め、各ステップで maxSum より大きければ更新していきます。これにより、配列を事前に一度走査するだけで答えが得られ、計算量は O(n) に抑えられます。

実装例

#include<iostream>
using namespace std;

int findMax(int a, int b){
    if(a > b)
        return a;
    return b;
}

int calculateMaxSum(int arr[], int n){
    int arraySum = 0, currentSum = 0, nextSum;
    for (int i = 0; i < n; i++){
        arraySum += arr[i];
        currentSum += i * arr[i];
    }
    int maxSum = currentSum;
    for (int i = 1; i < n; i++){
        nextSum = currentSum - (arraySum - arr[i-1]) + arr[i-1] * (n - 1);
        currentSum = nextSum;
        maxSum = findMax(maxSum, nextSum);
    }
    return maxSum;
}

int main(){
    int arr[] = {4, 8, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum sum of all the rotation of the array is " << calculateMaxSum(arr, n);
    return 0;
}

出力

The maximum sum of all the rotation of the array is 37

まとめ

配列の全回転における i * arr[i] の最大合計を求める問題では、全回転を個別に計算する O(n²) の単純な解法と、前回の回転の合計から次の合計を導き出す O(n) の効率的な解法があります。競技プログラミングや実務では、漸化式を活用した後者のアプローチが推奨されます。