Chương trình tìm chuỗi con 1 dài nhất sau khi xóa một phần tử bằng Python

Cho mảng nhị phân nums. Có thể xóa đúng một phần tử. Tìm độ dài chuỗi con toàn 1 dài nhất trong mảng kết quả. Nếu không có, trả về 0.

Ví dụ: nums = [1,0,1,1,1,0,1,1,0]. Xóa 0 tại vị trí 5 (chỉ số 0-based) → chuỗi con [1,1,1,1,1] độ dài 5.

Thuật toán giải quyết

• Nếu không có 0 trong nums: trả về len(nums) - 1 (bắt buộc xóa một 1).
• Nếu không có 1: trả về 0.
• Nén mảng thành danh sách a xen kẽ: [số 1 liên tiếp, 0, số 1 liên tiếp, 0, ...].
• Duyệt qua a, tại mỗi vị trí giá trị 0:
  • Nếu 0 ở đầu: max = max(max, a[1]).
  • Nếu 0 ở cuối: max = max(max, a[-2]).
  • Nếu 0 ở giữa: max = max(max, a[i-1] + a[i+1]) (ghép hai đoạn 1 liền kề).
• Trả về max.

Ví dụ triển khai

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

Đầu vào

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

Đầu ra

5