Bài toán dãy con lớn nhât

Trong chương 2 ta đã trình bày thuật toán chia để trị để giả bài toán dãy con lớn nhất với thời gian tính 0 (n log n). Bây giờ ta xét thuật toán quy hoạch động để giải bài toán này. Để đơn giản ta chỉ xét cách tính tổng của dãy con lớn nhất.

Phân rã. Gọi si là tổng của dãy con lớn nhất trong dãy

a1, a2, …., ai,

i = 1,2,…, n.Rõ ràng sn là giá trị cần tìm.

Tổng hợp lời giải. Trước hết, ta có sn = a1. Bây giờ giả sử i > 1 và sk là đã biết với k = 1,2,…, i - 1. Ta cần tính si là tổng của dãy con lớn nhất của dãy con lớn nhất của dãy a1, a2, …, ai-1, ai.

Rõ ràng dãy con lớn nhất của dãy này hoặc là có chứa phần tử ai hoặc là không chứa phần tử ai, vì thế chỉ có thể là một trong hai dãy sau đây:

• Dãy con lớn nhất của dãy a1, a2, …, ai-1.

• Dãy con lớn nhất của dãy a1, a2, …, ai kết thúc tại ai.

Từ đó suy ra

si = max {si-1,ei },

Trong đó ei là tổng của dãy con lớn nhất của dãy a1, a2, …, ai kết thúc tại ai.

Lưu ý rằng để tính ei, i = 1, 2, …, n, ta cũng có thể sử dụng công thức đệ quy sau:

e1 = a1;

ei = max {ai, ei-1 + ai }, i > 1.

Từ đó, ta có thuật toán sau để giải bài toán đặt ra:

procedure Maxsub(a);

begin

smax: = a[1]; (* smax - tổng của dãy con lớn nhất *)

maxendhere: = a[1];

imax: = 1; (* imax - vị trí kết thúc của dãy con lớn nhất )

for i: = 2 to n do

begin

u: = maxendhere + a[i];

v: = a[i];

if (u > v) then maxendhere = u else maxendhere = v;

if (maxendhere > smax) then

begin

smax: = maxendhere;

imax: = i;

end;

end;

end;

Dễ thấy thuật toán Maxsub có thời gian tính là O(n).