Pythonで配列内のすべての奇数長部分配列の合計を求める方法を解説

正の整数からなる配列 nums が与えられたとき、考えられるすべての奇数長の部分配列（サブ配列）の要素の合計を求めます。なお、部分配列とは元の配列から連続して取り出された部分列のことを指します。

具体例で確認する

例として、nums = [3, 8, 2, 5, 7] が入力された場合を考えてみましょう。このときの出力は 92 になります。対象となる奇数長の部分配列は以下の通りです。

nums[0] = 3
nums[1] = 8
nums[2] = 2
nums[3] = 5
nums[4] = 7
nums[0..2] → 合計 = 13
nums[1..3] → 合計 = 15
nums[2..4] → 合計 = 14
nums[0..4] → 合計 = 25

これらをすべて足し合わせると、3 + 8 + 2 + 5 + 7 + 13 + 15 + 14 + 25 = 92 となります。

解法のアプローチ

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

• 合計値 total を 0 で初期化する
• インデックス idx を 0 で初期化する
• 奇数の長さ（1, 3, 5, …）を格納したリスト l を作成する
• idx が l のサイズ未満である間、以下を繰り返す
  • k := l[idx] として、現在注目している部分配列の長さを取得する
  • i を 0 から nums のサイズまでループさせる
    • i + k < len(nums) + 1 を満たす場合、nums[i : i+k] の要素の合計を total に加算する
  • idx := idx + 1 として、次の奇数長へ進む
• 最後に total を返す

Pythonでの実装例

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

def solve(nums):
    total = 0
    idx = 0
    l = [i for i in range(len(nums)+1) if i % 2 != 0]

    while(idx < len(l)):
        k = l[idx]
        for i in range(len(nums)):
            if i+k < len(nums)+1:
                total += sum(nums[i:i+k])
        idx += 1
    return total

nums = [3,8,2,5,7]
print(solve(nums))

入力

[3,8,2,5,7]

出力

92

計算量と効率化のヒント

上記の実装では、奇数の長さごとに開始位置を走査し、さらにスライスの合計を計算するため、時間計算量は O(n³) になります。配列のサイズが大きくなると処理が遅くなる点に注意が必要です。

より効率化したい場合は、「各要素が奇数長の部分配列に何回登場するか」を数学的に求める方法が有効です。インデックス i（0始まり）の要素が含まれる奇数長の部分配列の個数は ((i+1) * (n-i) + 1) // 2 で表せるため、これを利用すると O(n) で答えを求められます。

def solve_fast(nums):
    n = len(nums)
    return sum(((i+1)*(n-i)+1)//2 * v for i, v in enumerate(nums))

nums = [3,8,2,5,7]
print(solve_fast(nums))  # 92

この最適化版でも同じ結果 92 が得られます。大きなデータを扱う場合や競技プログラミングでは、こちらのアプローチがおすすめです。