Link Sub: http://www.spoj.com/PTIT/problems/P146SUMA/
Người Gửi: WHquestion
- Problem:
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:
Số lượng số 1 nhiều nhất mà Tèo có thể có được.
Input
5
1 0 0 1 0
Output:
4
Input
4
1 0 0 1
Output:
4
- Solution:
Input
4
1 0 0 1
Output:
4
Vì n=100 nên ta có thể chạy hai vòng for xét các khoảng khác nhau. - Với mỗi khoảng cần phải đếm xem có bao nhiêu số 0 và bao nhiêu số 1. - Sau khi đếm thì giả sử abs(các phần tử - 1) sẽ có bao nhiêu con 1 trên cả dãy? - Và lưu lại số lượng số 1 nhiều nhất có được. *Chú ý: Như thầy TÍCH có comment thì bắt buộc phải chuyển ít nhất một phần tử. Nên nếu tất cả là 1 thì số lượng 1 Max-1.