# GÓC SÁNG TẠO > Khu vực lập trình > Pascal/Delphi/Kylix >  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);
> ...


_
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]

----------


## traihalinh

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


uhm.Thanks. Mình sẽ xem và điều chỉnh lại.

----------


## danlongthanh

Đúng là chương trình bác titi viết hơi lỗi , nếu như vậy thì tongmax không bao h < 0 . 
Có pro nào có cách khác không nhỉ ? Thanks .

----------


## kanhtran

F_: tổng các phần tử liên tiếp có phần tử cuối ở vị trí thứ i.
F=max(F[i-1]+A, A)
Không biết có sai không nhỉ :-ss_

----------


## meolamdep

> F_: tổng các phần tử liên tiếp có phần tử cuối ở vị trí thứ i.
> F=max(F[i-1]+A, A)
> Không biết có sai không nhỉ :-ss_


_
Mình test lại thì thấy đúng rùi. Độ phức tạp của thuật toán thì chắc là O(n). [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]_

----------


## datlinh1989

[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]) [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]) thuật toán đúng là O(N). Cứ sợ thuật toán sai mọi người cười [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])
Sắp tới mình xin nghỉ mod, nhưng nếu mọi người có bài nào khó cần giúp đỡ thì pm nick chat mình nhé. Xa diễn đàn cũng thấy nhớ.

----------


## ViệtNet

anh Giang này, đã bảo không xài Qhđ lại lao vào qhđ.
à, bài của titi_994 mình chạy test toàn bộ số âm thì ko đảm bảo nữa.
Vẫn là qhđ của anh chiếm ưu thế hơn [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------

