【Python】バイナリ配列で0を1に置き換えて最長の連続する1を実現するインデックスの求め方（Set-2）

問題の概要

0と1のみで構成されるバイナリ配列が与えられたとします。この配列の中から、ある1つの0を1に置き換えたときに、連続する1の並びが最も長くなる位置（インデックス）を見つけるのが本記事の課題です。

例えば、入力が [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1] の場合、答えは 10 になります。インデックス10の0を1に置き換えると、配列は [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1] となり、末尾に7個連続した1が並びます。

アルゴリズムの考え方

この問題は、配列を一度だけ走査（線形時間 O(n)）することで解くことができます。ポイントは、各0について「その左側に連続している1の個数（count_left）」と「右側に連続している1の個数（count_right）」を記録しておくことです。

ある0を1に置き換えると、その位置を挟んで左右の1がひとつにつながるため、連続する1の長さは「count_left + count_right + 1」として計算できます。この値が最大となる0の位置を追跡していきます。

手順の詳細

• i := 0、n := 配列Aのサイズとする
• count_left := 0、count_right := 0
• max_i := -1、last_i := -1、count_max := 0
• i < n の間、以下を繰り返す：
  • A[i] が 1 の場合：count_right を 1 増やす
  • A[i] が 0 の場合：
    • last_i が -1 でなければ（直前の0が存在すれば）、count_right + count_left + 1 が count_max より大きいとき、count_max と max_i を更新する
    • last_i := i とし、count_left := count_right に引き継ぎ、count_right := 0 にリセットする
  • i を 1 増やす
• ループ終了後も last_i が -1 でなければ、末尾部分について同様に count_max を比較・更新する
• 最後に max_i を返す

Pythonでの実装例

それでは、上記の手順を実際のPythonコードで確認してみましょう。

def find_max_one_index(A):
    i = 0
    n = len(A)
    count_left = 0
    count_right = 0
    max_i = -1
    last_i = -1
    count_max = 0
    while i < n:
        if A[i] == 1:
            count_right += 1
        else:
            if last_i != -1:
                if count_right + count_left + 1 > count_max:
                    count_max = count_left + count_right + 1
                    max_i = last_i
            last_i = i
            count_left = count_right
            count_right = 0
        i += 1
    if last_i != -1:
        if count_left + count_right + 1 > count_max:
            count_max = count_left + count_right + 1
            max_i = last_i
    return max_i

A = [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1]
print(find_max_one_index(A))

入力

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

出力

10

まとめ

このアルゴリズムでは、配列全体を1回走査するだけで答えが求まるため、計算量は O(n)、追加のメモリ使用量は O(1) と非常に効率的です。0が出現するたびに直前の0との間の1の個数を組み合わせて評価することで、「どの0を1に置き換えれば最長の連続する1が得られるか」を正確に特定できます。