Thuật toán Kadane trong C++ - Tìm tổng dãy con liên tiếp lớn nhất

Thuật toán Kadane giải quyết bài toán: Cho mảng số nguyên, tìm dãy con liên tiếp (subarray) có tổng lớn nhất. Độ phức tạp O(n) thời gian, O(1) không gian — tối ưu tuyệt đối.

Ý tưởng cốt lõi

Duyệt mảng, duy trì 2 biến:

• currentMax: Tổng lớn nhất của dãy con kết thúc tại vị trí hiện tại.
• globalMax: Tổng lớn nhất tổng quát tìm được cho đến nay.

Ví dụ cơ bản

#include <iostream>
#include <algorithm> // max
#include <climits>   // INT_MIN

using namespace std;

int kadane(const int arr[], int n) {
    int globalMax = INT_MIN; // Quan trọng: xử lý mảng toàn số âm
    int currentMax = 0;
    
    for (int i = 0; i < n; ++i) {
        currentMax = max(arr[i], currentMax + arr[i]);
        globalMax = max(globalMax, currentMax);
    }
    return globalMax;
}

int main() {
    int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Tong day con lon nhat: " << kadane(arr, n) << '\n'; // 7 (4, -1, -2, 1, 5)
    return 0;
}

Kết quả

Tong day con lon nhat: 7

Mở rộng: Trả về cả chỉ số dãy con

pair> kadaneWithIndices(const vector& arr) {
    int n = arr.size();
    int globalMax = INT_MIN, currentMax = 0;
    int start = 0, end = 0, tempStart = 0;
    
    for (int i = 0; i < n; ++i) {
        if (currentMax + arr[i] < arr[i]) {
            currentMax = arr[i];
            tempStart = i;
        } else {
            currentMax += arr[i];
        }
        
        if (currentMax > globalMax) {
            globalMax = currentMax;
            start = tempStart;
            end = i;
        }
    }
    return {globalMax, {start, end}};
}

Xử lý mảng toàn số âm

Khởi tạo globalMax = INT_MIN (hoặc arr[0]) và currentMax = 0 hoạt động đúng: thuật toán sẽ chọn phần tử lớn nhất (âm nhất nhỏ nhất) làm kết quả.

Biến thể: Tổng lớn nhất cho dãy con không rỗng vs có thể rỗng

• Không rỗng (mặc định): Khởi tạo globalMax = arr[0], currentMax = arr[0], duyệt từ i=1.
• Cho phép rỗng (tổng = 0): Khởi tạo globalMax = 0, currentMax = 0.

Ứng dụng thực tế

• Phân tích chuỗi thời gian (tìm khoảng lợi nhuận cao nhất).
• Xử lý ảnh (tìm vùng sáng nhất).
• Bioinformatics (tìm đoạn DNA điểm số cao).
• Bài toán biến thể: Maximum product subarray, Maximum sum rectangle in 2D matrix.

Lưu ý

• Kadane chỉ hoạt động cho mảng 1 chiều. Ma trận 2D dùng Kadane lồng nhau (O(n^3)).
• Nếu cần cả độ dài tối thiểu / tối đa, cần mở rộng trạng thái DP.

Kadane là thuật toán "must-know" cho mọi lập trình viên — đơn giản, tinh tế, và xuất hiện thường xuyên trong phỏng vấn và thi đấu lập trình.