Dãy con có tổng lớn nhất

Bài toán – Dãy con có tổng lớn nhất

Cho dãy gồm n số nguyên a₁, a₂, …, an. Tìm dãy con gồm một hoặc một số phần tử liên tiếp của dãy đã cho với tổng các phần tử trong dãy là lớn nhất.

Dữ liệu: Vào từ file văn bản SUBSEQ.INP

– Dòng đầu tiền chứa số nguyên d­ơng n (n < 10⁶).

– Dòng thứ i trong số n dòng tiếp theo chứa số ai (|ai|  1000).

Kết quả: Ghi ra file văn bản SUBSEQ.OUT

– Dòng đầu tiên ghi vị trí của phần tử đầu tiên của dãy con tìm được.

– Dòng thứ hai ghi vị trí của phần tử cuối cùng của dãy con tìm được

– Dòng thứ ba ghi tổng các phần tử của dãy con tìm được.

Thuật toán

Để giải bài toán này, ta sử dụng thuật toán Kadane.

Thuật toán Kadane là một thuật toán cực kỳ đơn giản và hiệu quả để tìm dãy con liên tiếp có tổng lớn nhất trong một dãy số nguyên cho trước. Thuật toán này được đặt theo tên của nhà khoa học người Ấn Độ – Subramanian Kadane.

Ý tưởng của thuật toán là duyệt qua các phần tử của dãy một cách tuần tự, với mỗi phần tử ta tính tổng của dãy con liên tiếp kết thúc bằng phần tử đó. Nếu tổng này lớn hơn tổng lớn nhất đã biết trước đó thì ta cập nhật tổng lớn nhất và vị trí của dãy con liên tiếp đó.

Cụ thể, ta duyệt qua dãy số một cách tuần tự và sử dụng hai biến để lưu trữ thông tin về dãy con liên tiếp có tổng lớn nhất. Biến max_sum lưu trữ tổng lớn nhất đã tìm được cho đến thời điểm hiện tại, còn biến cur_sum lưu trữ tổng của dãy con liên tiếp kết thúc bằng phần tử hiện tại. Ta cũng sử dụng hai biến start_idx và end_idx để lưu trữ vị trí bắt đầu và kết thúc của dãy con liên tiếp tương ứng.

Thuật toán Kadane có độ phức tạp thời gian là O(n), nghĩa là nó có thể tìm ra dãy con liên tiếp có tổng lớn nhất trong thời gian tuyến tính với số phần tử của dãy.

Cài đặt bài toán với Python

with open('SUBSEQ.INP', 'r') as f:
    n = int(f.readline())
    a = list(map(int, f.readlines()))

max_sum = a[0]
cur_sum = a[0]
start_idx = 0
end_idx = 0
cur_start_idx = 0

for i in range(1, n):
    if cur_sum < 0:
        cur_sum = a[i]
        cur_start_idx = i
    else:
        cur_sum += a[i]

    if cur_sum > max_sum:
        max_sum = cur_sum
        start_idx = cur_start_idx
        end_idx = i

with open('SUBSEQ.OUT', 'w') as f:
    f.write(str(start_idx + 1) + '\n')  # Vị trí bắt đầu
    f.write(str(end_idx + 1) + '\n')  # Vị trí kết thúc
    f.write(str(max_sum) + '\n')  # Tổng lớn nhất

Cài đặt bài toán với C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("SUBSEQ.INP", "r", stdin);
    freopen("SUBSEQ.OUT", "w", stdout);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int max_sum = a[0];
    int cur_sum = a[0];
    int start_idx = 0;
    int end_idx = 0;
    int cur_start_idx = 0;

    for (int i = 1; i < n; i++) {
        if (cur_sum < 0) {
            cur_sum = a[i];
            cur_start_idx = i;
        } else {
            cur_sum += a[i];
        }

        if (cur_sum > max_sum) {
            max_sum = cur_sum;
            start_idx = cur_start_idx;
            end_idx = i;
        }
    }

    cout << start_idx + 1 << endl; // Vị trí bắt đầu
    cout << end_idx + 1 << endl; // Vị trí kết thúc
    cout << max_sum << endl; // Tổng lớn nhất

    return 0;
}