Pythonですべての連続する部分配列の合計を求めるプログラム

問題概要

数値のリスト nums が与えられたとき、その中のすべての連続する部分配列(サブリスト)を考えます。それぞれの部分配列の合計を計算し、さらにそれらの総和を求めます。最後に、結果を 10 ** 9 + 7(1,000,000,007)で割った余りを返します。

例えば、入力が nums = [3, 4, 6] の場合、出力は 43 になります。考えられる部分配列は以下の通りです。

• [3]
• [4]
• [6]
• [3, 4]
• [4, 6]
• [3, 4, 6]

これらすべての合計を足すと 3 + 4 + 6 + 7 + 10 + 13 = 43 となります。

解法のアプローチ

すべての部分配列を実際に生成して合計を計算することも可能ですが、リストが長くなると計算量が膨大になります。そこで、各要素が何個の部分配列に含まれるかを数学的に数えることで、O(N) の効率的な解法を実現できます。

インデックス i の要素に注目すると、この要素を含む部分配列の数は次のように求められます。

• 部分配列の開始位置として選べるのは、0 から i までの (i + 1) 通り
• 部分配列の終了位置として選べるのは、i から N-1 までの (N - i) 通り

したがって、インデックス i の要素は合計 (i + 1) × (N - i) 個の部分配列に登場します。この値を各要素に掛けて足し合わせれば、答えが得られます。

アルゴリズムの手順

• N := nums のサイズとする
• ans := 0 で初期化する
• i を 0 から nums のサイズまで繰り返す
  • n := nums[i]
  • ans := ans + (i + 1) × (N - i) × n
• (ans mod 1000000007) を返す

それでは、理解を深めるために以下の実装例を見てみましょう。

実装例(Python)

class Solution:
    def solve(self, nums):
        N = len(nums)
        ans = 0
        for i in range(len(nums)):
            n = nums[i]
            ans += (i + 1) * (N - i) * n
        return ans % 1000000007

ob = Solution()
print(ob.solve([3, 4, 6]))

入力

[3, 4, 6]

出力

43

まとめ

この手法では、全部分配列を列挙する O(N²) 以上のアプローチと異なり、各要素の出現回数を一度計算するだけで済むため、時間計算量 O(N) で効率的に答えを求められます。大きなリストに対しても高速に動作し、結果を 10⁹ + 7 で割ることでオーバーフローを防いでいる点もポイントです。