Pythonでリスト全体の合計よりも厳密に大きい合計を持つ部分リストが存在するか判定するプログラム

数値のリスト nums が与えられたとき、リスト全体の合計値よりも厳密に大きい合計を持つ部分リスト(連続する要素の並び)が存在するかどうかを判定する問題を考えます。

たとえば、nums = [1, -2, 3, 4] の場合を見てみましょう。リスト全体の合計は 6 ですが、部分リスト [3, 4] の合計は 7 となり、6 を上回っています。したがって、この場合の出力は True になります。

解法のアプローチ

この問題は、累積和を利用することで効率的に解くことができます。手順は以下のとおりです。

• リストの先頭から順に要素を加算していき(累積和を計算)、途中で合計が負になったら True を返す

• 続いて、リストの末尾から順に同様の処理を行い、合計が負になったら True を返す

• どちらの走査でも条件を満たさなかった場合は False を返す

なぜこの方法で判定できるのか?

先頭からの累積和(接頭辞の合計)がある時点で負になるなら、「残り部分(接尾辞)の合計 = 全体の合計 − 接頭辞の合計」は全体の合計よりも厳密に大きくなります。末尾からの累積和についても同様のことが言えます。さらに、全体の合計を超える部分リストが存在するなら、必ずそのような接頭辞か接尾辞が存在することが示せるため、前後それぞれ一度の走査だけで判定が完了します。

実装例

class Solution:
    def solve(self, nums):
        total = sum(nums)
        s = 0
        for i in nums:
            s += i
            if s < 0:
                return True
        s = 0
        i = len(nums) - 1
        while i > -1:
            s += nums[i]
            if s < 0:
                return True
            i = i - 1
        return False

ob1 = Solution()
nums = [2, -4, 3, 5]
print(ob1.solve(nums))

なお、変数 total はリスト全体の合計を保持していますが、このアルゴリズムでは累積和の符号判定だけで十分なため、実際の判定処理では直接使用されません。

このアルゴリズムの計算量は O(n) であり、リストを前方向と後方向にそれぞれ一度ずつ走査するだけなので、非常に効率的です。

入力

[2, -4, 3, 5]

出力

True

この例では、リスト全体の合計は 6 ですが、部分リスト [3, 5] の合計は 8 となり、6 よりも大きいため True が出力されます。