Bài 2. Dãy đèn (HSG THPT TP. Cần Thơ 2026)
Xem dạng PDFCho một dãy gồm ~n~ bóng đèn, mỗi bóng đèn được điều khiển trạng thái bởi một công tắc riêng biệt là bật hoặc tắt. Nếu đèn đang ở trạng thái bật thì được ký hiệu là 1, ngược lại nếu tắt được ký hiệu là 0. Người điều khiển được phép thực hiện thao tác sau đúng một lần: chọn một đoạn các bóng đèn liên tiếp đang ở trạng thái tắt và chuyển tất cả chúng sang trạng thái bật.
Yêu cầu: Hãy đưa ra số lượng lớn nhất các bóng đèn liên tiếp nhau ở trạng thái bật, sau khi người điều khiển thực hiện thao tác trên một cách tối ưu.
Dữ liệu vào
Gồm hai dòng:
- Dòng đầu tiên ghi số ~n (n \le 2 \times 10^5)~.
- Dòng tiếp theo lần lượt ghi các trạng thái của bóng đèn là 0 hoặc 1, mỗi số cách nhau một dấu cách.
Kết quả
Một số nguyên là kết quả tìm được, nếu không thể thao tác thì in ra −1.
Ví dụ
Input 1
5
1 0 0 1 0
Output 1
4
Input 2
3
1 1 1
Output 2
-1
Ở ví dụ 1, bật hai đèn ở vị trí 2 và 3 tạo thành đoạn bật 1 1 1 1 gồm 4 đèn. Ở ví dụ 2, không có đèn nào đang tắt nên không thực hiện được thao tác.
Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).