BÀI 4. (5,0 điểm) TỔNG LỚN NHẤT
Tranh thủ trong giờ ra chơi, hai bạn Nam và Bình rủ nhau chơi trò 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, Nam viết số thứ nhất, Bình viết số thứ hai, rồi đến lượt Nam viết số thứ ba,… Cứ tiếp tục như vậy hai bạn viết được một dãy gồm n số a1, a2, …, an . Đến đây hai bạn chưa kịp chơi trò chơi của mình thì đã đến giờ học. Thầy vào lớp, sẳn thấy dãy số trên bảng, thầy đã đặt ra câu đố: Tìm một đoạn liên tiếp các số 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 được đáp án. Bạn hãy lập trình giải giúp các bạn trong lớp nhé.
Dữ liệu vào: Cho từ tệp văn bản có tên BL4.INP có dạng như sau:
- Dòng đầu tiên ghi số nguyên n (1≤n≤1000)
- Dòng thứ hai ghi dãy n số nguyên a1, a2, …, an (-1000 ≤ ai ≤ 1000, i=1..n)
Kết quả: Ghi ra tệp văn bản có tên BL4.OUT gồm một số nguyên duy nhất là tổng lớn nhất của một đoạn liên tiếp các số trong dãy.
Ví dụ:
| BL4.INP | BL4.OUT |
10 2 -9 4 1 -3 5 8 -7 3 1 | 15 |
pascal nha giup mik vs a
Program HOC24;
const fi='BL4.INP' ;
fo='BL4.OUT' ;
var f: text;
a: array[1..1000] of integer;
j,i,n,max: integer;
t: longint;
procedure ip;
begin
assign(f,fi);
reset(f);
readln(f,n);
for i:=1 to n do read(f,a[i]);
close(f);
end;
procedure out;
begin
assign(f,fo);
rewrite(f);
i:=1; max:=0;
while (i<=n) do
begin
t:=0;
for j:=i+1 to n do
begin
t:=t+a[j];
if t>max then max:=t;
end;
i:=i+1;
end;
write(f,max);
close(f);
end;
begin
ip;
out;
end.
