Chương trình C++ tìm tổng mảng con lớn nhất O(n²) (phương pháp đơn giản)

Chúng ta sẽ phát triển chương trình C++ tìm tổng mảng con lớn nhất với độ phức tạp O(n²) (phương pháp đơn giản/naive).

Thuật toán

Bắt đầu
  Nhập các phần tử mảng.
  Tạo vòng lặp cho độ dài mảng con từ 1 đến n, trong vòng lặp này,
    Tạo vòng lặp lồng nhau, tính tổng mảng con đầu tiên với độ dài đó.
    Với các mảng con còn lại, cộng phần tử tiếp theo vào tổng và trừ phần tử đầu tiên của mảng con đó.
    So sánh với max toàn cục và cập nhật nếu lớn hơn.
    In mảng con lớn nhất và tổng của chúng.
Kết thúc.

Mã ví dụ

#include <iostream>
using namespace std;

int main() {
    int n, i, j, m = -1, s, ini_m, fi_m;
    cout << "\nNhập số phần tử dữ liệu trong mảng: ";
    cin >> n;
    int a[n];
    for(i = 0; i < n; i++) {
        cout << "Nhập phần tử " << i+1 << ": ";
        cin >> a[i];
    }
    for(i = 1; i < n+1; i++) {
        s = 0;
        for(j = 0; j < n; j++) {
            if(j < i)
                s += a[j];
            else
                s = s + a[j] - a[j-i];
            if(m < s) {
                ini_m = j-i+1;
                fi_m = j;
                m = s;
            }
        }
    }
    cout << "\nMảng con lớn nhất là: ";
    for(i = ini_m; i <= fi_m; i++)
        cout << a[i] << " ";
    cout << "\nTổng mảng con lớn nhất là: " << m;
    return 0;
}

Kết quả đầu ra

Nhập số phần tử dữ liệu trong mảng: 10
Nhập phần tử 1: 1
Nhập phần tử 2: -2
Nhập phần tử 3: 3
Nhập phần tử 4: -4
Nhập phần tử 5: 5
Nhập phần tử 6: -6
Nhập phần tử 7: 7
Nhập phần tử 8: 8
Nhập phần tử 9: -9
Nhập phần tử 10: 10
Mảng con lớn nhất là: 7 8 -9 10
Tổng mảng con lớn nhất là: 16