Pythonで回転配列の最大加重和を効率的に求めるプログラム

いくつかの要素からなる配列があるとします。この配列をさまざまな位置で回転させたとき、得られる加重和の最大値を求めたいと思います。

配列 nums の加重和 S は、次の式で定義されます。

$$\mathrm{S=\sum_{i=1}^{n}i \times nums[i]}$$

つまり、各要素にその位置(インデックス+1)を掛けて足し合わせたものが加重和です。

具体例

入力が L = [5, 3, 4] の場合、出力は 26 になります。それぞれの回転状態における加重和は以下の通りです。

• 配列が [5, 3, 4] の場合:5 + 2×3 + 3×4 = 5 + 6 + 12 = 23

• 配列が [3, 4, 5] の場合:3 + 2×4 + 3×5 = 3 + 8 + 15 = 26(最大)

• 配列が [4, 5, 3] の場合:4 + 2×5 + 3×3 = 4 + 10 + 9 = 23

効率的な解法のポイント

すべての回転パターンに対して毎回加重和を一から計算すると、時間計算量は O(n²) になってしまいます。しかし、回転による加重和の変化には規則性があります。

配列を1つ左に回転させると、それまで位置 i+1 にあった要素は位置 i に移動するため、全体の加重和から「全要素の合計(sum_a)」だけ減少し、末尾へ移動した先頭要素は「要素値 × n」だけ加算されます。この関係を利用すれば、前の加重和から O(1) で次の加重和を求められ、全体の計算量を O(n) に抑えられます。

アルゴリズムの手順

• n := nums のサイズ
• sum_a := nums の全要素の合計
• ans := Σ nums[i] × (i + 1)(初期加重和)
• cur_val := ans
• i を 0 から n-1 まで繰り返す:
  • cur_val := cur_val − sum_a + nums[i] × n
  • ans := ans と cur_val のうち大きい方
• ans を返す

Pythonでの実装例

理解を深めるために、実際のコードを見てみましょう。

def solve(nums):
    n = len(nums)
    sum_a = sum(nums)
    cur_val = ans = sum(nums[i] * (i + 1) for i in range(n))

    for i in range(n):
        cur_val = cur_val - sum_a + nums[i] * n
        ans = max(ans, cur_val)

    return ans

nums = [5, 3, 4]
print(solve(nums))

入力

[5,3,4]

出力

26

まとめ

この手法では、回転ごとに加重和を再計算せず、差分だけで更新できるため、O(n) の時間計算量で最大加重和を効率的に求めることができます。配列のサイズが大きい場合でも高速に動作するのが大きなメリットです。