#include <iostream>

using namespace std;

// Hàm tìm dãy con có tổng lớn nhất
void timDayConTongLonNhat(int arr[], int n) {
    int maxEndingHere = arr[0];
    int maxSoFar = arr[0];
    int batDau = 0, ketThuc = 0;
    int tempBatDau = 0;

    for (int i = 1; i < n; ++i) {
        if (arr[i] > (maxEndingHere + arr[i])) {
            maxEndingHere = arr[i];
            tempBatDau = i;
        } else {
            maxEndingHere += arr[i];
        }

        if (maxEndingHere > maxSoFar) {
            maxSoFar = maxEndingHere;
            batDau = tempBatDau;
            ketThuc = i;
        }
    }

    cout << "Dãy con có tổng lớn nhất là: ";
    for (int i = batDau; i <= ketThuc; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    cout << "Tổng của dãy con là: " << maxSoFar << endl;
}

int main() {
    int arr[] = {1, -2, 3, 4, -1, 2, 1, -5, 4}; // Thay đổi dãy số nguyên tùy ý
    int n = sizeof(arr) / sizeof(arr[0]);

    timDayConTongLonNhat(arr, n);

    return 0;
}