C++でarr[i]*iの合計を最大化する方法

問題の概要

N個の整数からなる配列が与えられます。配列の要素は自由に並べ替えることができます。そのうえで、Σarr[i] * i(i = 0, 1, 2, ... n-1)の最大値を求めるのが課題です。

例えば、入力配列が {4, 1, 6, 2} の場合、要素を昇順に並べ替えることで最大値28が得られます。

{1, 2, 4, 6} = (1 * 0) + (2 * 1) + (4 * 2) + (6 * 3) = 28

アルゴリズム

この問題は、次の手順で解くことができます。

1. 配列を昇順にソートする
2. 配列を走査し、各要素にインデックスi(0, 1, 2, ..., n-1)を掛けて合計する
3. 合計値を返す

なぜ昇順ソートが最適なのでしょうか。理由はシンプルで、大きな値ほど大きなインデックスと掛け合わせたほうが合計が大きくなるためです。もし小さな値が後ろに配置されると、それをより大きな値と入れ替えたときに必ず合計が増加するため、昇順配置が理論上の最大値となります。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n){
    sort(arr, arr + n);
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        sum = sum + arr[i] * i;
    }
    return sum;
}
int main(){
    int arr[] = {4, 1, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum sum = " << getMaxSum(arr, n) << endl;
    return 0;
}

出力結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Maximum sum = 28

計算量について

このアルゴリズムの時間計算量はO(n log n)で、これはソート処理のコストが支配的であるためです。ソート後の走査は線形時間O(n)で完了します。また、追加のメモリを使用しないため、空間計算量はO(1)です。