Đoạn con có tổng lớn nhất

BÀI TOÁN

Cho một dãy gồm n số nguyên a1, a2, …, an. Hãy tìm một đoạn con (dãy gồm các phần tử liên tiếp nhau) có tổng lớn nhất.

Dữ liệu vào:

• Dòng đầu ghi số n
• Dòng thứ hai ghi n số nguyên a1, a2, …, an, mỗi số có giá trị tuyệt đối không vượt quá 1000.

Kết quả:

Ghi ra 1 số là tổng lớn nhất tìm được.

Ví dụ:

Input

10

1 3 -5 2 7 6 -2 4 -3 1

Output

17

Giới hạn:

• 50% số test có n ≤ 10³
• 50% số test còn lại có n ≤ 10⁶

 

HƯỚNG DẪN

Cách tiếp cận đơn giản nhất ta tìm tổng từng đoạn và so sánh các kết quả này để tìm ra kết quả lớn nhất. Độ phức tạp cho cách này là O(n³), cách này chưa thể giải quyết cho bài toán trên.

Để cải tiến thuật toán trên, ta tính nhanh tổng của một đoạn bất kỳ bằng cách làm như sau:

• Gọi f[i] là tổng i phần tử đầu tiên, f[i] được tính như sau:
•      f[0] = 0
•      f[i] = f[i-1] + a[i]
• Tổng các phần tử từ i đến j là: f[j] – f[i-1]

Với cách cải tiến, độ phức tạp của thuật toán giảm từ O(n³) xuống còn O(n²) và ta có thể giải quyết được 50% số test của bài toán trên.

Để có thể giải quyết được 100% số test trên ta có 2 cách làm với độ phức tạp O(n) như sau:

Cách 1

Ta sử dụng biến sum để giữ giá trị tổng tiềm năng của các phần tử liên tục phía trước (khi thêm tổng này vào đoạn mới phía sau ta luôn nhận được một đoạn có tổng lớn hơn). Ta nhận thấy khi giá trị của sum < 0 thì ta sẽ cập nhật lại giá trị sum = 0 (bỏ đi đoạn phía trước).

Đoạn code cho ý tưởng trên như sau:

    int maxsum = 0;

    int sum = 0;

    for (int i = 1; i <= n; ++i) {

        sum += a[i];

        if (sum < 0) sum = 0;

        maxsum = max(sum, maxsum);

    }

Cách 2 (thanks to Xuân Quang  and Văn Thiên)

Ta nhận thấy, tại mỗi vị trí thứ i tổng của đoạn lớn nhất kết thúc tại i là f[i] – min(f[j] | j = 0..i).

Khi đó, ta lần lượt xét các vị trí i, tại mỗi vị trí thứ i ta giữ lại giá trị nhỏ nhất của các f[j].

Đoạn code cho ý tưởng trên như sau:

    f[0] = 0;

    for (int i = 1; i <= n; ++i) f[i] = f[i-1] + a[i];

    int maxsum = 0, f_min = 0;

    for (int i = 1; i <= n; ++i) {

        f_min = min(f_min, f[i]);

        maxsum = max(maxsum, f[i] - f_min);

    }