Lại là Trò chơi mới

Submit solution
Points: 3 (partial)
Time limit: 1.0s
Memory limit: 98M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

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<=105)
  • 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:

Copy
4

1 0 0 1

Output:

Copy
4
tichpx

Comments


  • 0
    NguyenHongSon_CNTT3_K62  commented on Feb. 13, 2022, 4:00 a.m.

    Mn cho em xin thuật toán tối ưu bài này với ạ!!


    • 3
      sguenm  commented on Feb. 13, 2022, 10:36 a.m.

      cái dãy ấy chính là dãy cần chuyển đổi 0<->1


    • 3
      sguenm  commented on Feb. 13, 2022, 10:34 a.m.

      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