Về thuật toán Kadane

[rogp10]

Mảng con của mảng A là mảng gồm các phần tử [A[i], A[i+1], …, A[j]], 1 <= i <= j <= |A|, kí hiệu A[i…j].
Quy ước A[1…|A|] = A (1-based array).

Thuật toán Kadane là thuật toán dùng để tìm mảng con có tổng lớn nhất, và có thể mở rộng với điều kiện dãy có k phần tử trở lên hay mảng nhiều chiều. Thuật toán ban đầu được đặt ra cho ảnh bitmap (2D). Đây là giả mã của thuật toán 1D.

-> A[1..N]
: max_so_far = max_ending_here = A[1]
: max(a, b) = a if(a > b) else b
for i:=2 to N do
   max_ending_here := max(max_ending_here + A[i], A[i])
   max_so_far := max(max_ending_here, max_so_far)
<- max_so_far

Dựa trên cơ sở nào mà nó đúng? Ta có hai bất biến sau:

• max_ending_here là max tổng các mảng con A[m…i] m <= i.
• max_so_far là max tổng các mảng con của A[1…i].

Như vậy có thể giải thích:

Do mảng con có tính liên tục nên với mỗi phần tử A[i] ta chỉ có hai lựa chọn: một là cộng thêm A[i] vào mảng con max A[m…i-1], hai là bỏ luôn, chỉ lấy A[i].

Trông khó hiểu và không thuyết phục đúng không? Nhưng thuật toán Kadane đã xét tất cả các mảng con rồi!

Có hai cách duyệt mảng con, cách 1 đã rất quen thuộc:

for i:=1 to N do
   for j:=i to N do
     // các mảng A[i..i], A[i..i+1], ..., A[i..N]

Cách 2 lại ít ai nghĩ đến và ta sẽ phân tích nó:

for i:=1 to N do
  for j:=1 to i do
    // A[1..i], A[2..i], ..., A[i..i]

Ta kí hiệu S_{mn} = \sum_{m \le n} A[m..n] và M_n = \max(S_{mn}). M_n đóng vai trò của max_ending_here trong giả mã ở đầu bài.

Ta có M_{n+1} = \max(S_{1(n+1)}, S_{2(n+1)}, ..., S_{n(n+1)}, S_{(n+1)(n+1)})\\ = \max(S_{1(n+1)}, S_{2(n+1)}, ..., S_{n(n+1)}, A_{n+1})
mà S_{m(n+1)} = S_{mn} + A_{n+1} (định nghĩa S)
và \max({x: x \in S}) + m = \max({x+m: x \in S}) do tính đơn điệu của phép cộng số
nên M_{n+1} = \max(\max(S_{1n}, S_{2n}, ..., S_{nn}) + A_{n+1}, A_{n+1}) = \max(M_{n} + A_{n+1}, A_{n+1}) Q.E.D.

hay max_ending_here = max(max_ending_here + A[i], A[i]). ∎

	A[1]	A[2]	A[3]	...	A[N-1]	A[N]
M1	S11
M2	S12	S22
M3	S13	S23	S33
...	...	...	...	...	...	...
MN-1	S1(N-1)	S2(N-1)	S3(N-1)	...	S(N-1)(N-1)
MN	S1N	S2N	S3N	...	S(N-1)N	SNN