Dãy con dài nhất có tổng bằng 0

ai giải thích giùm mình cái code này với ạ:v đề là
cho dãy gồm N(N<=10000)số a1,a2,…,aN.hãy tìm dãy con liên tiếp dài có tổng nhất bằng 0

var a,s:array[0..100] of integer;
n,i,j,max,vt:integer;
begin
write('N=');readln(n);
for i:=1 to n do
begin
write('a[',i,']=');readln(a[i]);
inc(s[i],s[i-1]+a[i]);
end;
for i:=1 to n do
for j:=0 to i-1 do
if (s[i]-s[j]=0) and (i-j>max) then
begin
max:=i-j;
vt:=j;
end;
for i:=vt+1 to max+vt do write(a[i],' ');
readln;
end.

s[i] = sigma(ii=1…n) a[ii]
vậy s[i] - s[j] bằng :smiley:

có thể nói ý tưởng code này giúp mình đc ko ạ

Dễ chứng minh

s[i] = a[1] + a[2] + ... + a[i]

Từ đó ta có:

s[i] = a[1] + a[2] + ... + a[i]
s[j] = a[1] + a[2] + ... + a[i] + a[i+1] + ...+ a[j]
=> s[j] - s[i] = a[i+1] + ... + a[j]
  • Nếu s[j] -s[i] = 0 <=> a[i+1] + … + a[j] = 0 , độ dài doạn [i+1,j] = j-(i+1)+1 =j-i
    so sánh tất cả các đoạn bằng 2 vòng for i,j để tìm đoạn dài nhất

  • Có thể cải tiến thuật toán thành O(nlogn) nếu dùng tìm kiếm nhị phân, hoặc O(n) nếu dùng hash table

1 Like

Dùng cây tự cân bằng với khóa là tổng và lưu vị trí đầu tiên có tổng này để được O(nlogn) và mem là (8+theta(1))*n byte.

1 Like

Gió ơi! Cho tuj hỏi nếu dùng tìm kiếm nhị phân sao thế ông.
Tạo ra mảng temp[i] = temp[i-1] + a[i], rồi sort mảng temp[] . Binary_search xem có phần tử giống nhau hã .Rồi làm sao xuất ra mảng con dài nhất .
Tuj chưa hiểu mình sẽ thiết kế bài này theo tìm kiếm nhị phân như thế nào?
Tks nhé !!

Nếu dùng sắp xếp thì đặt a là struct có index và sum. Sau đó sắp xếp ưu tiên cho sum.

Ủa rogp10 ơi.
Nếu mình sắp xếp array xong. Sort xong thì nếu temp[i] == temp[i+1] thì mình xuất ra temp[i].index thôi chứ. Mình phải tìm kiếm nhị phân để làm gì zậy (tui chưa hiểu dùng tìm kiếm nhị phân chổ nào hết). -_-
Cảm ơn nhé!

Ủa rogp10 ơi.
Nếu mình sắp xếp array xong. Sort xong thì nếu temp[i] == temp[i+1] thì mình xuất ra temp[i].index thôi chứ. Mình phải tìm kiếm nhị phân để làm gì zậy (tui chưa hiểu dùng tìm kiếm nhị phân chổ nào hết). -_-
Cảm ơn nhé!

Không cần phải tìm kiếm gì cả :smiley: nếu bạn so sánh đúng khi sắp xếp thì sau đó duyệt 1 lượt là xong.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?