5.Trò chơi mới


Submit solution

Points: 3 (partial)
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type

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 <= 100)\)
  • 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


  • 0
    TICHPX  commented on March 14, 2019, 4:56 a.m.

    Bài này nâng cấp lên \(n=10^5\) cho khí thế