Cấu trúc dữ liệu và Giải thuật Bài 19: Bài toán kinh điển: Tìm mảng con có tổng lớn nhất (Kadane's Algorithm).

Hãy tưởng tượng bạn đang phân tích biểu đồ lợi nhuận tài chính của một công ty trong 30 ngày. Có những ngày lãi đậm (số dương), nhưng cũng có những ngày lỗ nặng (số âm). Sếp giao cho bạn một nhiệm vụ: "Hãy tìm ra một giai đoạn liên tiếp (từ ngày A đến ngày B) mang lại tổng lợi nhuận cao nhất".

Đây chính là phiên bản thực tế của bài toán Maximum Subarray Problem (Tìm mảng con liên tiếp có tổng lớn nhất) – một trong những câu hỏi phỏng vấn kinh điển nhất mọi thời đại tại các tập đoàn công nghệ. Và chìa khóa để giải quyết nó nằm ở một thuật toán mang tên tác giả của nó: Thuật toán Kadane.

1. Hiểu đúng về "Mảng con liên tiếp" (Contiguous Subarray)

Sự khác biệt lớn nhất giữa Mảng con (Subarray) và Tập con (Subsequence) là tính liên tục. Cho mảng A = [-2, 1, -3, 4, -1, 2, 1, -5, 4].

Tập con có thể nhặt các số ngẫu nhiên: [1, 4, 2, 4] (tổng = 11). Nhưng đây KHÔNG phải là điều bài toán yêu cầu.
Mảng con bắt buộc phải nằm liền kề nhau giống như một đoạn cắt ra từ mảng gốc: [4, -1, 2, 1] (tổng = 6).

2. Thảm họa của tư duy Brute Force

Cách nghĩ tự nhiên nhất là tính tổng của tất cả các mảng con có thể tạo ra, sau đó xem cái nào lớn nhất. Bạn dùng 2 vòng lặp lồng nhau: Vòng lặp ngoài chọn điểm bắt đầu i, vòng lặp trong chọn điểm kết thúc j. Với mỗi cặp (i, j), bạn lại có một mảng con.

Độ phức tạp: Khối lượng phép tính sẽ lên tới $O(n^2)$ . Nếu phân tích dữ liệu chứng khoán trong 10 năm (khoảng 3650 ngày), số phép tính là hơn 13 triệu. Nếu phân tích tín hiệu cảm biến IoT (hàng triệu điểm dữ liệu), server của bạn sẽ treo ngay lập tức.

3. Thuật toán Kadane: Đỉnh cao của sự tối giản

Vào năm 1984, Giáo sư Jay Kadane đã đưa ra một thuật toán giải quyết bài toán này chỉ với một vòng lặp duy nhất ( $O(n)$ ) và không tốn thêm dung lượng bộ nhớ nào ( $O(1)$ ).

Bản chất của thuật toán Kadane nằm ở một câu hỏi tư duy cực kỳ sắc bén tại mỗi bước đi:

"Tôi nên gắn mình vào mảng con của người đi trước, hay tôi nên tự bắt đầu một mảng con mới của riêng mình?"

Giả sử chúng ta duyệt mảng từ trái sang phải. Tại một vị trí i bất kỳ, ta có một biến current_max (Tổng lớn nhất tính đến thời điểm hiện tại).

Nếu current_max của những ngày trước đang là số âm, việc cộng thêm nó vào ngày hiện tại arr[i] chỉ làm cho ngày hiện tại bị "kéo lùi" xuống. Lúc này, ta nhẫn tâm vứt bỏ quá khứ, bắt đầu một mảng con mới chính tại arr[i].
Nếu current_max đang là số dương, nó đang tạo ra "đà tăng trưởng". Ta tiếp tục cộng arr[i] vào current_max (ngay cả khi arr[i] là số âm, vì biết đâu ngày mai lại là một số dương khổng lồ bù đắp lại).

4. Công thức toán học cốt lõi

Thuật toán Kadane thực chất là một dạng tối giản của Quy hoạch động (Dynamic Programming), với phương trình trạng thái:current_max = MAX(arr[i], current_max + arr[i])

Đồng thời, ta dùng thêm một biến global_max để liên tục ghi nhận lại đỉnh cao nhất từng đạt được trong suốt quá trình duyệt.

5. Triển khai thuật toán bằng Golang

Hãy xem đoạn code cực kỳ ngắn gọn nhưng mang sức mạnh $O(n)$ này:

func maxSubArray(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    // Khởi tạo cả 2 biến bằng phần tử đầu tiên
    currentMax := nums[0]
    globalMax := nums[0]
    
    // Bắt đầu duyệt từ phần tử thứ hai
    for i := 1; i < len(nums); i++ {
        // Quyết định: Kéo dài mảng con cũ, hay bắt đầu mảng con mới?
        if currentMax + nums[i] > nums[i] {
            currentMax = currentMax + nums[i]
        } else {
            currentMax = nums[i]
        }
        
        // Cập nhật kỷ lục cao nhất nếu cần
        if currentMax > globalMax {
            globalMax = currentMax
        }
    }
    
    return globalMax
}

Mô phỏng (Dry Run) với mảng [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

Bắt đầu: current = -2, global = -2
i=1 (Số 1): current cũ là -2 (số âm). Cộng vào thành -1, thà lấy luôn số 1 còn hơn. $\rightarrow$ current = 1, global = 1. (Bắt đầu chuỗi mới)
i=2 (Số -3): current cũ là 1 (dương). Gắn -3 vào $\rightarrow$ current = -2, global = 1.
i=3 (Số 4): current cũ là -2 (âm). Bỏ chuỗi cũ, lấy số 4 $\rightarrow$ current = 4, global = 4. (Lại bắt đầu chuỗi mới)
i=4 (Số -1): current cũ là 4 (dương). Gắn -1 vào $\rightarrow$ current = 3, global = 4.
i=5 (Số 2): current cũ là 3 (dương). Gắn 2 vào $\rightarrow$ current = 5, global = 5. (Phá kỷ lục!)
i=6 (Số 1): current cũ là 5. Gắn 1 vào $\rightarrow$ current = 6, global = 6. (Phá kỷ lục!)

Kết quả cuối cùng globalMax là 6, tương ứng với đoạn [4, -1, 2, 1].

6. Tại sao Kadane lại quan trọng?

Thuật toán Kadane dạy cho các kỹ sư phần mềm một triết lý thiết kế hệ thống quan trọng: Đôi khi, bạn không cần phải lưu trữ toàn bộ lịch sử để đưa ra quyết định tốt nhất ở hiện tại.

Bằng cách chỉ mang theo trạng thái tối ưu liền kề (Local Optimum - currentMax), chúng ta tiết kiệm được toàn bộ không gian RAM (biến bài toán từ $O(n)$ Space xuống còn $O(1)$ Space) mà vẫn đảm bảo tìm ra được kết quả tối ưu toàn cục (Global Optimum - globalMax).

Chúng ta vừa giải quyết thành công một bài toán tối ưu trên mảng một chiều. Ở bài học tiếp theo, chúng ta sẽ khép lại Chương 2 bằng một bài toán kinh điển khác thường gặp trong các hệ thống lên lịch trình (Calendar/Scheduling): Xử lý các khoảng thời gian bị chồng chéo lên nhau.

cấu trúc dữ liệu