BÀI TẬP 67: BÀI TOÁN TÌM SỐ (DÃY CON CÓ TỔNG LỚN NHẤT)

Tranh thủ trong giờ ra chơi, hai bạn Khang và Nam rủ nhau chơi trò chơi tìm số. Hai bạn lần lượt mỗi người viết một số nguyên lên bảng, Khang viết số thứ nhất, Nam viết số thứ hai, rồi đến lượt Khang viết số thứ ba,... Cứ tiếp tục như vậy hai bạn viết được một dãy số gồm n số a₁, a₂,..., a_n. Khi hai bạn chưa kết thúc trò chơi của mình thì đã đến giờ học, giáo viên vào lớp thấy dãy số trên bảng, giáo viên đặt ra câu đố: “tìm một đoạn các số liên tiếp trong dãy số trên sao cho tổng giá trị các số trong đoạn đó là lớn nhất". Vì dãy số có quá nhiều số nên cả lớp nhìn hoa cả mắt mà vẫn chưa tìm ra đáp án. Bạn hãy lập trình giải câu đổ trên giúp các bạn trong lớp nhé.

Input: cho từ tệp văn bản TONG.INP gồm:

- Dòng đầu tiên ghi số nguyên n (1≤n≤1000).

- Dòng thứ hai ghi dãy n số nguyên a₁, a₂,..., a_n

Output: ghi ra tệp văn bản TONG.OUT gồm:

- Dòng thứ nhất ghi tổng lớn nhất của đoạn các số liên tiếp trong dãy.

- Dòng thứ hai ghi vị trí bắt đầu của đoạn tìm được.

- Dòng thứ ba ghi chiều dài của đoạn tìm được.

Ví dụ:

TONG.INP	TONG.OUT
10 2 -9 4 1 -3 5 8 -7 3 1	Xau con co tong lon nhat: 15 Bat dau tu vi tri: 3 Dai: 5

CODE THAM KHẢO:

program xaucon_tonglonnhat;

var a:array[1..1000] of longint;

    i,n,s,sum,vtd,vtc,tam: longint;

begin

        assign(input,'tong.inp'); reset(input);

        assign(output,'tong.out'); rewrite(output);

        readln(n);

        for i:=1 to n do read(a[i]);

        vtd:=0; vtc:=0; s:=0; sum:=-3200; tam:=0;

        for i:=1 to n do

        begin

                if a[i] > s+a[i] then

                begin

                        tam:=i;

                        s:=a[i];

                end else s:=s+a[i];

                if sum < s then

                begin

                        sum:=s;

                        vtd:=tam;

                        vtc:=i;

                end;

        end;

        writeln('Xau con co tong lon nhat: ',sum);

        writeln('Bat dau tu vi tri: ',vtd);

        writeln('Dai: ',vtc-vtd+1);

        close(input); close(output);

end.