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ế