Tìm chỉ số 0 cần thay bằng 1 để có dãy 1 liên tiếp dài nhất - Set 2 trong Python

Cho mảng nhị phân, tìm vị trí của 0 mà khi thay bằng 1 sẽ cho dãy 1 liên tiếp dài nhất.

Ví dụ: [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1] → Vị trí 10 (dãy thành [1,1,0,0,1,0,1,1,1,1,1,1,1]).

Thuật toán O(n) một lần duyệt

1. Duyệt mảng, giữ count_left (số 1 liên tiếp trước 0 trước đó), count_right (số 1 liên tiếp sau 0 hiện tại).
2. Khi gặp 0: nếu đã có 0 trước (last_i != -1), tính count_left + count_right + 1, cập nhật max và vị trí max_i.
3. Cập nhật last_i, count_left = count_right, count_right = 0.
4. Sau vòng lặp, kiểm tra lại cho 0 cuối cùng.

Ví dụ code

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))

Input

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

Output

10