Pythonで1つの要素を削除した後に現れる「1」のみの最長部分配列を求めるアルゴリズム

問題の概要

0と1だけで構成されるバイナリ配列 nums が与えられます。この配列から要素を1つだけ削除できるとき、削除後の配列内に存在する「1のみを含む最長の空でない部分配列(サブアレイ)」の長さを求めます。該当する部分配列が存在しない場合は 0 を返します。

例えば、入力が nums = [1,0,1,1,1,0,1,1,0] の場合を考えてみましょう。位置5(0始まりのインデックス)にある 0 を削除すると、[1,1,1,1,1] という「1が5個連続した部分配列」が得られるため、出力は 5 となります。

解法の考え方

この問題は、連続する1の「かたまり(ラン)」ごとに数え直すことで効率的に解けます。手順は以下の通りです。

• 配列に 0 が一切含まれない場合 → 全体が1の連なりなので、len(nums) - 1(1つ削除するため)を返します。
• 配列に 1 が一切含まれない場合 → 条件を満たす部分配列は作れないので 0 を返します。
• 新しいリスト a を用意し、カウンタ cnt を 0 で初期化します。
• 配列の各要素 i について走査します。
  • i == 0 のとき:これまでの cnt が 0 でなければリスト a の末尾に追加し、cnt をリセット。その後、0 自身も a に追加します。
  • i == 1 のとき:cnt を +1 します。
• 走査終了後、cnt が残っていれば a の末尾に追加します。
• こうして a には「1の連続数」と「0」が交互に格納されます。
• 最大値 Max を 0 で初期化し、a の各要素を確認します。
  • a[i] が 0 以外ならスキップ。
  • a[i] == 0 かつ i が末尾のとき → 直前のラン長 a[i-1] と比較。
  • a[i] == 0 かつ i が先頭のとき → 直後のラン長 a[i+1] と比較。
  • それ以外の 0 のとき → 両隣のラン長の和 a[i+1] + a[i-1](この 0 を削除すると2つのランが結合するため)と比較します。
• 最後に Max を返します。

実装例(Python)

def solve(nums):
   if 0 not in nums:
      return len(nums)-1
   if 1 not in nums:
      return 0
      a = []
      cnt = 0
      for i in nums:
         if i == 0:
            if cnt != 0:
               a.append(cnt)
               cnt = 0
            a.append(i)
         else:
            cnt += 1
      if cnt!=0:
         a.append(cnt)
      Max = 0
      for i in range(len(a)):
         if a[i] != 0:
            continue
         if a[i] == 0 and i == len(a)-1:
            Max = max(Max,a[i-1])
         elif a[i] == 0 and i == 0:
            Max = max(Max,a[i+1])
         elif a[i] == 0:
            Max = max(Max,a[i+1]+a[i-1])
   return Max

nums = [1,0,1,1,1,0,1,1,0]
print(solve(nums))

入力

[1,0,1,1,1,0,1,1,0]

出力

5

計算量について

このアルゴリズムは配列を2回走査するだけなので、時間計算量は O(n)、圧縮結果を保存するための補助リストが必要ですが、空間計算量も O(n) に収まります。スライディングウィンドウを使えば補助リストなしで O(1) 追加空間に抑えることも可能です。