01/10/2018, 09:59

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.

rogp10 viết 12:11 ngày 01/10/2018

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

nắng viết 12:12 ngày 01/10/2018

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

Gió viết 12:15 ngày 01/10/2018

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

rogp10 viết 12:02 ngày 01/10/2018

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.

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

nắng

0 chủ đề

0 bài viết

Tác giả nổi bật