Cho chuoi so, yeu cau tim chuoi con co gia tri lon nhat. Voi do phuc tap O(n). Ai biet xin chi giup!
(To Tran Tung, VNN1)
Chao ban!
Day la thuat toan tim tong con lon nhat toi viet bang C/C++ . Input cua no se la array float a[n] va out put se la
max : gia tri lon nhat cua day con
trai : dau trai cua day con
phai : dau phai cua day con
Y tuong cua no la neu [trai,phai] la doan day con co gia tri lon nhat thi [trai,phai] cung hoac la day con lon nhat cua a[n-1] hoac phai = n-1 va [trai,phai-1] la day con lon nhat trong so nhung day con nam o phia duoi cua a[n-1] . Nhu vay o moi vong lap, [phai,trai] la day con lon nhat cua a[i] ( gia tri nay la max) va [trai2,i-1] la day con co gia tri lon nhat trong so nhung day co mot dau la i-1 ( gia tri nay la max_right).
| Mã lệnh (C) |
float max = 0, max_right = 0;
int phai = 0, trai = 0, trai2 = 0; for ( int i = 0; i < size; i++ ) { if ( a[i] + max_right > max ) { max_right += a[i]; max = max_right; trai = trai2; phai = i; } else if ( a[i] + max_right > 0 ) { max_right += a[i]; } else { max_right = 0; right = i; } |
(Do Xuan Phuong, VNN1)
I have to go in few minutes. The ideas are there, but there may be some errors.
Var
i,n,tong,gtong,dau,cuoi,gdau,gcuoi:integer;
a:array[1..100] of integer;
begin
readln(n);
for i:= 1 to n do readln(a[i]);
tong:=0;
dau:=1;
cuoi:=1;
gtong:=0;
for i:=1 to n do
begin
tong:=tong+a[i];
if tong>gtong then
begin
gdau:=dau;
gcuoi:=cuoi;
gtong:=tong;
end;
if tong<0 then {important bit is here!!!}
begin
tong:=0;
dau:=i+1;
cuoi:=i+1;
end else cuoi:=i;
end;
writeln('dau',gdau,'cuoi',gcuoi,'tong',gtong);
readln;
end.
By the way, I nearly killed myself, five years ago when I was walking in the street and thinking about the program. Hope that it is what you want.