Về thuật toán Kadane

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 A[m..n], m \le nM_n = \max(S_{mn}). Mn đó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})
S_{m(n+1)} = S_{mn} + A_{n+1} (định nghĩa S)
\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
10 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?