Pythonで積が正になる部分配列の最大長を求めるアルゴリズムを解説

問題概要

整数の配列 nums が与えられたとき、「すべての要素の積が正になる部分配列（サブ配列）」のうち、最も長いものの長さを求めることを考えます。

例えば、入力が nums = [2, -2, -4, 5, -3] の場合、答えは 4 になります。先頭の4つの要素からなる部分配列 [2, -2, -4, 5] の積は 2 × (-2) × (-4) × 5 = 80 となり、正の値になるためです。ここに5番目の要素 -3 を加えると負の数が3つになり積が負になってしまうため、長さ4が最大となります。

解法のポイント

この問題を効率よく解く鍵は、次の2つの性質にあります。

• 負の数の個数が0個または偶数個なら、その区間全体の積は必ず正になる
• 0 が1つでも含まれると積は必ず 0 になるため、0 を境界として配列をいくつかの区間に分割して考える

負の数が奇数個含まれる区間では、区間の端にある「最初の負の数」または「最後の負の数」のどちらか一方を除外すれば、残りの負の数は偶数個となり、積を正にできます。除外する位置によって得られる長さが異なるため、両方の候補を比較して大きい方を採用します。

アルゴリズムの手順

1. 補助関数 util(s, e)

区間 [s, e] について、積が正になる最大の部分配列の長さを返す関数を定義します。

1. 負の数のカウンタ neg を 0、最初の負の数の位置 ns と最後の負の数の位置 ne を -1 で初期化します。
2. i を s から e まで走査し、nums[i] が負であれば neg を +1 し、ns が未設定なら ns = i とし、さらに ne = i を毎回更新します。
3. neg が 0 または偶数であれば、区間全体をそのまま使えるので e - s + 1 を返します。
4. neg が奇数であれば、max(e - ns, ne - s)、すなわち「最初の負の数を除いた長さ」と「最後の負の数を除いた長さ」の大きい方を返します。

2. メイン処理 solve()

1. 答え ans を 0、区間の開始位置 s と終了位置 e を -1 で初期化します。
2. 配列を先頭から走査し、0 以外の要素に出会ったとき、まだ区間が始まっていなければ s を設定します。
3. 0 を検出した時点で、直前までの区間 [s, i-1] に対して util() を呼び出し、その結果を ans に反映したうえで s, e をリセットします。
4. 走査完了後に未処理の区間が残っている場合は、配列末尾までの区間に対して同じく util() を呼び出します。
5. 最後に ans を返します。

実装例

以上の考え方をPythonで実装すると、次のようになります。

def util(s, e):
    neg = 0
    ns, ne = -1, -1
    for i in range(s, e + 1):
        if nums[i] < 0:
            neg += 1
            if ns == -1:
                ns = i
            ne = i

    # 負の数が0個または偶数個なら区間全体が利用可能
    if neg % 2 == 0:
        return e - s + 1
    else:
        # 奇数個の場合は、端の負の数をどちらか1つ除外する
        return max(e - ns, ne - s)

def solve(nums):
    ans = 0
    s, e = -1, -1

    for i in range(len(nums)):
        if nums[i] != 0 and s == -1:
            s = i
        elif nums[i] == 0 and s != -1:
            e = i - 1
            ans = max(ans, util(s, e))
            s = -1
            e = -1

    if s != -1 and e == -1:
        e = len(nums) - 1
        ans = max(ans, util(s, e))

    return ans

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

入力

[2, -2, -4, 5, -3]

出力

4

計算量

各要素は高々2回程度しか走査されないため、時間計算量は O(n)、追加で必要な空間計算量は O(1) で済みます。0 を境に配列を分割し、各区間内で負の数の偶奇だけを管理するシンプルな戦略が、この問題を線形時間で解くポイントです。