Pythonで部分配列の合計をmで割った余りの最大値を求めるプログラム

問題の概要

n個の要素からなる配列 nums と整数 m が与えられたとき、任意の部分配列（連続する要素の集合）の合計を m で割った余りの最大値を求めることを考えます。

たとえば、nums = [1,5,7,3]、m = 5 が入力として与えられた場合、出力は 3 になります。すべての部分配列について余りを計算すると、次のようになります。

• [1] mod 5 = 1
• [5] mod 5 = 0
• [7] mod 5 = 2
• [3] mod 5 = 3
• [1,5] mod 5 = 1
• [5,7] mod 5 = 2
• [7,3] mod 5 = 0
• [1,5,7] mod 5 = 3
• [5,7,3] mod 5 = 0
• [1,5,7,3] mod 5 = 1

この中で最大となるのは 3（[3] および [1,5,7] の場合）です。

解法のポイント：累積和と二分探索

すべての部分配列を全列挙すると計算量は O(n²) となり、n が大きい場合は非現実的です。そこで活躍するのが累積和（プレフィックスサム）と二分探索の組み合わせです。

区間 [i+1, j] の部分配列の合計は「j番目までの累積和 − i番目までの累積和」で表せます。mod m の世界では、差が負になった場合に m を足して正の値に戻せるため、「小さい累積和から大きい累積和を引いて m を加えた値」の方が大きくなることがあります。

この性質を利用し、各累積和 s に対して「s より大きい最小の累積和」を二分探索で見つければ、(s − その値) % m が取り得る最大の候補となります。これにより全体の計算量を O(n log n) に抑えられます。

アルゴリズムの手順

具体的には、次の手順で問題を解きます。

1. csum := リストを作成し、最初に nums[0] % m を格納する
2. nums の2番目以降の各要素 x について、(csum の末尾の値 + x) % m を csum の末尾に追加する
3. seen := 初期値として 0 のみを含むリストを用意する（先頭から始まる部分配列を考慮するため）
4. max_sum := -1 で初期化する
5. csum の各要素 s について以下を繰り返す：
   • idx := seen に s を挿入してもソート順が保たれる最左位置（bisect_left）を求める
   • idx < len(seen) の場合：max_sum を max(max_sum, s, (s − seen[idx]) % m) で更新する
   • それ以外の場合：max_sum を max(max_sum, s) で更新する
   • bisect.insort_left(seen, s) で s を seen に挿入する
6. max_sum を返す

実装例

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

import bisect

def solve(nums, m):
    csum = [nums[0] % m]
    for x in nums[1:]:
        csum.append((csum[-1] + x) % m)

    seen = [0]
    max_sum = -1
    for s in csum:
        idx = bisect.bisect_left(seen, s)
        if idx < len(seen):
            max_sum = max(max_sum, s, (s - seen[idx]) % m)
        else:
            max_sum = max(max_sum, s)
        bisect.insort_left(seen, s)

    return max_sum

nums = [1, 5, 7, 3]
m = 5
print(solve(nums, m))

入力

nums = [1, 5, 7, 3], m = 5

出力

3

計算量

各累積和ごとに二分探索を1回行うため、時間計算量は O(n log n) です。また、累積和リストとソート済みの seen リストの保存に O(n) の空間計算量が必要です。全列挙による O(n²) のアプローチと比べ、大幅に高速化できる点が大きなメリットです。

まとめ

mod m における部分配列合計の最大化問題は、累積和の差と二分探索を組み合わせることで効率的に解けます。「負の差に m を足す」という mod 演算特有の性質を意識することが、この種の問題を解くうえでの重要なコツです。標準ライブラリの bisect モジュールを使えば、ソート済みリストへの挿入も簡潔に実装できます。