Dãy con có tổng lớn nhất, Ai yêu Pascan mời vô ^^!

[tranngoan]

Dãy con có tổng lớn nhất, Ai yêu Pascan mời vô ^^!

Cho dãy gồm n số nguyên a1,a2,a3,...,an . Tìm dãy con gồm một hoặc một số phần tử liên tiếp của dãy đã cho với tổng các phần tử trong dãy là lớn nhất .

Dữ liệu vào : 1 số nguyên dương n<10^6

Dòng thứ i trong số n dòng tiếp theo chứa số -1000<ai<1000

Kết quả : dòng đầu ghi vị trí phần tử đầu tiên của dãy tìm được
Dòng 2 ghi vị trí phần tử cuối của dãy tìm được
Dòng 3 ghi tổng các phần tử của dãy con tìm được

VD: In: 10
1 5 8 -34 -70 -4 56 2 8 -300
Out : 7
9
66
Bài này đã được titi_994 giải bên dưới, ai có cách giải hay hơn cứ post nhé ^^! Thanks

[vAPK]

Đúng bài mình cũng đang hóc :|

[kevinvu1987]

Các prô đâu hết cả rồi ^^! Zô nào ! Bài này là bài thi HSG gì gì đó [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] . Thanks các prô trước nha .

[phamthaovnn]

Mình vết bằng Turbo nên không cho số lớn n lớn hơn được.
Các bạn xem thử

uses crt;
var i,n,tong,tongmax,dau,gtdau,cuoi,gtcuoi:integer;
a:array[1..10000] of integer;
BEGIN
clrscr;
readln(n);
writeln('-------');
for i:=1 to n do readln(a);
tong:=0;
dau:=1;
cuoi:=n;
tongmax:=0;
for i:=1 to n do
begin
tong:=tong+a;
if tong>tongmax then
begin
gtdau:=dau;
gtcuoi:=cuoi+1;
tongmax:=tong;
end;
if tong<0 then
begin
tong:=0;
dau:=i+1;
cuoi:=n-1;
end
else cuoi:=i;
end;
writeln('-------');
writeln(gtdau);
writeln(gtcuoi);
writeln(tongmax);
readln;
END.

[chungcunhavuong]

Bạn nói thử cách làm của bạn xem, nếu là O(NlogN) thì mình không nói cách của mình nữa, nếu là O(N^2) thì mình sẽ nói cách của mình.

[myhanh2365]

Không cần Qhd đâu bạn. Bạn cứ lấy nháp ra và thử làm theo cách này nhé, bạn ngẫm 1 lát sẽ hiểu vì sao nó hoạt động tốt:
_ Tạo mảng F là mảng tổng các phần từ tử 1-> i.
_ Tìm trong F dãy con không liên tiếp giảm dần có số thứ tự là nhỏ nhất (lưu ý chưa chắc nó đã là dãy con dài nhất, chỉ cần nhỏ nhất thôi).
_ Các vị trí mình lấy ở F để tạo dãy con như trên CÓ THỂ là vị trí liền trước của phần tử đầu tiên của dãy con thỏa mãn. (xét riêng trường hợp đặc biệt dãy con bắt đầu từ 1 nhé).
_ Công việc còn lại chỉ là tìm kiếm vị trí cuối tương ứng với các vị trí đầu có thể được đó, so sánh để tìm dãy con dài nhất. Việc tìm kiếm này có thể dùng tìm kiếm nhị phân cho nhanh ^^.
Bạn nháp ra nhé, lấy nhiều test vào, nghĩ sâu nghĩ kĩ sẽ ngấm, chứ mình giải thích có khi bạn khó hiểu hơn [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
Thêm chút : lần sau bạn post code lên diễn đàn cố gắng post thuật toán trước, code sau nhé, chứ post code không khó hiểu lắm [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] mình cũng chưa hiểu thuật toán của bạn lắm. Nhưng hình như thuật toán của bạn O(N) mà :-ss

[hocnauan]

À, sr bạn nha, mình nhầm sang bài của mình ^^. Bài mình đang gặp là tìm dãy con liên tiếp có tổng > 1 số M cho trước. Còn bài của bạn thuật toán bạn dùng là O(N) thì ok rồi, chỉnh nữa làm gì cho mất công.

[Minhpham.vcu]

Mình vết bằng Turbo nên không cho số lớn n lớn hơn được.
Các bạn xem thử

uses crt;
var i,n,tong,tongmax,dau,gtdau,cuoi,gtcuoi:integer;
a:array[1..10000] of integer;
BEGIN
clrscr;
readln(n);
writeln('-------');
for i:=1 to n do readln(a);
tong:=0;
dau:=1;
cuoi:=n;
tongmax:=0;
for i:=1 to n do
begin
tong:=tong+a;
if tong>tongmax then
begin
gtdau:=dau;
gtcuoi:=cuoi+1;
tongmax:=tong;
end;
if tong<0 then
begin
tong:=0;
dau:=i+1;
cuoi:=n-1;
end
else cuoi:=i;
end;
writeln('-------');
writeln(gtdau);
writeln(gtcuoi);
writeln(tongmax);
readln;
END.

Bạn thử với test này xem:
2
-1
-2
Chương trình của bạn ra
0
0
0

[sonhp]

Ginta_ITFam là anh Giang phải không nhỉ???

[manhvlance]

Ừ là anh, nhưng em là ai thế? Người quen nhận nhau thì gửi tin nhắn riêng em nhé, post bài qua topic là anh del liền đấy [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]