หาตำแหน่ง 0 ที่ควรเปลี่ยนเป็น 1 ให้ได้ลำดับ 1 ติดกันยาวที่สุด (Python)

โจทย์: อาร์เรย์ไบนารี หา index ของ 0 ที่ถ้าเปลี่ยนเป็น 1 จะได้ consecutive 1s ยาวที่สุด

ตัวอย่าง: [1,1,0,0,1,0,1,1,1,1,0,1,1] → index 10 → [1,1,0,0,1,0,1,1,1,1,1,1,1] (ยาว 7)

อัลกอริทึม One Pass

1. count_left = จำนวน 1 ติดกันก่อน 0 ล่าสุด
2. count_right = จำนวน 1 ติดกันหลัง 0 ล่าสุด (กำลังนับอยู่)
3. last_i = index ของ 0 ล่าสุด
4. เมื่อเจอ 0 ใหม่: ตรวจสอบ count_left + count_right + 1 > max → อัปเดต max_i = last_i
5. อัปเดต count_left = count_right, count_right = 0, last_i = i
6. หลังลูป ตรวจสอบครั้งสุดท้ายสำหรับ 0 ตัวสุดท้าย

ตัวอย่างโค้ด

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
    
    # ตรวจสอบ 0 ตัวสุดท้าย
    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))  # 10

ผลลัพธ์

10

สรุป: One pass O(n) time O(1) space ติดตามความยาว 1s ระหว่าง 0s คำนวณความยาวรวมถ้าเปลี่ยน 0 ตัวกลาง