Pythonで長さxとyの重ならない2つのサブリストの最大合計を求める方法

問題概要

数値のリスト nums と整数 x、y が与えられたとき、それぞれ長さが x と y であり、互いに重なり合わない2つのサブリスト（部分リスト）を選び、その要素の合計の最大値を求めるのが今回の課題です。

たとえば、nums = [3, 2, 10, -2, 7, 6]、x = 3、y = 1 という入力の場合、出力は 22 になります。これは、長さ3のサブリストとして [3, 2, 10] を、もう一方として [7] を選んだ場合の合計（15 + 7 = 22）に該当します。

解法のアプローチ：累積和（Prefix Sum）を活用

この問題は、累積和を使うことで線形時間 O(n) で解くことができます。まず、リスト A の累積和を格納したリスト P を作成しておけば、任意の連続区間の合計を P[j] − P[i] という差分で即座に取得できるようになります。

具体的な手順は以下のとおりです。

1. 累積和の構築： 要素0のみを含むリスト P を用意し、A の各要素 x に対して「P の末尾要素 + x」を追加していきます。
2. solve 関数の定義： 引数として2つの長さ len1、len2 を受け取ります。「長さ len1 のサブリストが左側・長さ len2 のサブリストが右側」という配置を想定します。
3. 各区間合計の算出： Q を「P[i + len1] − P[i]」（開始位置 i における長さ len1 の区間の合計）のリストとして生成します。
4. プレフィックス最大値の作成： Q のコピーである prefix を作り、隣接要素同士を比較して「その位置までの最大値」に書き換えます。
5. 答えの更新： ans を負の無限大で初期化し、右側サブリストの開始位置 i を len1 から len(P) − len2 まで動かしながら、「left（左側区間の合計の最大値）+ right（P[i + len2] − P[i]）」との最大値で ans を更新します。
6. メイン処理： solve(len1, len2) と solve(len2, len1) の大きい方を返します。これにより、「x のサブリストが左にある場合」と「y のサブリストが左にある場合」の両方をカバーできます。

実装コード

以下が実際の Python コードです。

class Solution:
    def solve(self, A, len1, len2):
        # 累積和の作成
        P = [0]
        for x in A:
            P.append(P[-1] + x)

        def solve(len1, len2):
            # 長さ len1 の全区間の合計
            Q = [P[i + len1] - P[i] for i in range(len(P) - len1)]
            # プレフィックス最大値
            prefix = Q[:]
            for i in range(len(prefix) - 1):
                prefix[i + 1] = max(prefix[i + 1], prefix[i])

            ans = float("-inf")
            # 右側サブリストの開始位置を走査
            for i in range(len1, len(P) - len2):
                left = prefix[i - len1]
                right = P[i + len2] - P[i]
                ans = max(ans, left + right)
            return ans

        return max(solve(len1, len2), solve(len2, len1))

ob = Solution()
nums = [3, 2, 10, -2, 7, 6]
x = 3
y = 1
print(ob.solve(nums, x, y))

入力

[3, 2, 10, -2, 7, 6], 3, 1

出力

22

計算量について

累積和の構築、プレフィックス最大値の作成、および本体のループはいずれもリスト長に比例して処理されるため、全体の時間計算量は O(n)、空間計算量も O(n) となります。すべての組み合わせを総当たりする O(n²) の素朴なアプローチと比べて大幅に高速で、大きな入力サイズでも安心して利用できます。