Lại là Trò chơi mới
Vừa mới thất tình nên quá buồn chán, Mr.Duy tự nhốt mình trong phòng và phát minh ra một trò chơi mới trên giấy để chơi.
Mr.Duy viết n số nguyên \(a1,a2, ... an\). Mỗi chữ số có giá trị \(0\) hoặc \(1.\) Anh ta thực hiện đúng 1 bước duy nhất: chọn 2 số nguyên \(i,j (1<= i <= j <= n)\) và thay đổi tất cả giá trị \(a[k]\) trong phạm vi \([i,j] ( i <= k <= j).\) Thay đổi giá trị của \(x\) có nghĩa là thay giá trị \(x = 1 - x.\)
Mục tiêu cuối cùng của trò chơi là sau chính xác đúng một bước như trên thì chúng ta có được tối đa có thể số lượng chữ số 1 trong dãy.Vì quá nhiều tiên nên Duy tự nhủ rằng, Nếu ai có thể giải quyết được trò chơi này bằng cách viết 1 chương trình tìm ra số lượng tối đa nhất có thể của các chữ số 1 này với mỗi dãy tương ứng thì Duy sẽ tặng người đó 500k. Kiếm tiền tiêu tết thật ez.
Input:
- Dòng đầu tiên là số nguyên \(n (1 <= n <= 10^5)\)
- Dòng thứ hai là \(n\) số nguyen \(a[1], a[2], ... a[n]\) có giá trị \(0\) hoặc \(1.\)
Output:
- Số nguyên duy nhất - Số lượng tối đa có thể của chữ số 1 sau chính xác 1 bước biến đổi.
Example:
Input:
4
1 0 0 1
Output:
4
Comments
Mn cho em xin thuật toán tối ưu bài này với ạ!!
cái dãy ấy chính là dãy cần chuyển đổi 0<->1
mình nghĩ quy ước 0 = +1 và 1 = -1 rồi tìm dãy con có tổng lớn nhất là được
Em cảm ơn anh ạ, giờ em thử làm lại ạ!