P146SUMA spoj PTIT – Chuyển đổi

Nguồn đề bài: http://www.spoj.com/PTIT/problems/P146SUMA/

1. Đề bài P146SUMA spoj

Tèo đang chơi một trò chới với dãy số. Dãy số của Tèo chỉ gồm các số 0 hoặc 1. Tèo đang cần chuyển đổi một đoạn của dãy số để sao cho số lượng số 1 là nhiều nhất.

Chuyển đổi một đoạn là thay các số a[i]  trong đoạn đó bằng số x, với x = 1 – a[i].

Các bạn giúp Tèo chọn đoạn để chuyển đổi nhé.

Input

Dòng đầu tiên là số nguyên n (1 <=n <= 100).

Dòng thứ hai là dãy số của Tèo.

Output

Số lượng số 1 nhiều nhất mà Tèo có thể có được.

Example

Test 1:

Input:

5

1 0 0 1 0

Output:

4

 

Test 2:

Input:

4

1 0 0 1

Output:

4

2. Gợi ý P146SUMA spoj PTIT

Với n<=100 bài này có thể dễ dàng áp dụng duyệt O(n^3).

3. Code tham khảo P146SUMA spoj PTIT

2 thoughts on “P146SUMA spoj PTIT – Chuyển đổi

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *