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

const   fi='';
        nmax=100;
type    data=longint;
var
        f:text;
        A:array[1..nmax+2] of byte;
        n:data;
        dem:data;
procedure docfile;
var     i:data;
begin
        dem:=0;
        assign(f,fi); reset(f);
        readln(f,n);
        for i:=1 to n do
                begin
                        read(f,a[i]);
                        if a[i]=1 then
                                inc(dem);
                end;
end;

procedure xuli;
var     i,j,k,tmp,res:data;
begin
        res:=0;
        for i:=1 to n do
                for j:=i to n do
                        begin
                                tmp:=dem;
                                for k:=i to j do
                                        if a[k]=1 then
                                                dec(tmp)
                                        else
                                                inc(tmp);
                                if tmp>res then
                                        res:=tmp;
                        end;
        writeln(res);
end;

begin
        docfile;
        xuli;
end.