3. Cộng dồn

3. Cộng dồn
Trong quá trình tính toán, nếu biết tổ chức dữ liệu có tính toán kế thừa thì số lượng
phép tính giảm đi rõ rệt.
Ví dụ 1. Tổng k số nguyên liên tiếp lớn nhất
Cho một mảng A gồm N số nguyên và số nguyên dương k. Hãy tìm tổng k số nguyên
liên tiếp của mảng A lớn nhất.
Input: nhập từ file dayso.inp, dòng đầu là hai số n, k; Dòng dau là dãy A
Output: Đưa ra file dayso.out ba số nguyên i,j,T, trong đó i là chỉ số đầu, j là chỉ số cuối
của đoạn k phần tử, T là tổng lớn nhất.
Phân tích
Bình thường ta phải tính tổng tất cả các đoạn con có k phần tử liên tiếp, rồi so sánh
các tổng này để tìm ra tổng lớn nhất. Công việc này đòi hỏi (N-k) (k-1) phép cộng và tổ hợp
2
CN k
phép so sánh hai tổng. Nếu N và k tương đối lớn thì số lượng phép tính này rất lớn. Độ
phức tạp tính toán trung bình cỡ O(Nk).
Để giải bài toán này, còn cách sau đây có độ phức tạp tính toán trung bình là O(N): Ta
tạo các tổng Si= A1+A2+…+Ai=Si-1+Ai . Sau đó muốn tìm các tổng k phần tử liên tiếp bắt đầu từ
j ta sử dụng công thức:
Aj+Aj+1+…+Aj+k-1=(A1+A2+…+Aj+k-1)-(A1+A2+…+Aj-1)=Sj+k-1-Sj-1, với 1 jN-k+1.
Văn bản chương trình.
Program Tong_K_so_nguyên;
const fi = 'dayso.in';
fo = ‘dayso.out’;
nmax=10000;
var n, k, be, en : integer;
max : longint;
a : array[1..nmax] of integer;
s : array[0..nmax] of longint;
Procedure doc_input;
var f : text; i : integer;
begin
assign(f,fi); reset(f);
read(f,n,k);
for i:=1 to n do read(f,a[i]);
close(f);
s[0] := 0;
for i:=1 to n do s[i] := s[i-1] + a[i];
end;
var j : integer;
BEGIN
doc_input;
max := -maxlongint;
for j:= 1 to n-k+1 do
if max<s[j+k-1]-s[j-1] then begin
max := s[j+k-1]-s[j-1];
be :=j;
en := j+k-1;
end;
write(be,' ',en,' ',max);
readln;
END.