Tổng lớn nhất của dãy con liên tiếp (Kadane)

Cho mảng số nguyên (có thể âm), tìm dãy con liên tiếp có tổng lớn nhất. Đây là bài toán kinh điển giải quyết bằng thuật toán Kadane (quy hoạch động tuyến tính).

Đầu vào và Đầu ra

Đầu vào: {-2, -3, 4, -1, -2, 1, 5, -3}
Đầu ra: Maximum Sum = 7 (dãy con: 4, -1, -2, 1, 5)

Thuật toán

Duy trì hai 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.
• tempMax: tổng lớn nhất tổng thể tìm được cho đến nay.

Cập nhật: currentMax = max(arr[i], currentMax + arr[i]), tempMax = max(tempMax, currentMax).

Ví dụ C++

#include <iostream>
using namespace std;

int maxSum(int arr[], int n) {
    int tempMax = arr[0], currentMax = tempMax;
    for (int i = 1; i < n; i++) {
        currentMax = max(arr[i], currentMax + arr[i]);
        tempMax = max(tempMax, currentMax);
    }
    return tempMax;
}

int main() {
    int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = 8;
    cout << "Maximum Sum of the Sub-array is: " << maxSum(arr, n);
}

Kết quả

Maximum Sum of the Sub-array is: 7