Editorial for sub: Dãy con và đoạn con

Hiểu bài toán

Bài toán yêu cầu tìm hai giá trị trên một dãy số:

1. Tổng lớn nhất của dãy con khác rỗng: Dãy con là tập hợp các phần tử không nhất thiết liền kề nhau. Để có tổng lớn nhất, ta chỉ cần cộng tất cả các số dương trong dãy lại với nhau. Nếu dãy chỉ toàn số âm, ta phải chọn số âm lớn nhất (gần 0 nhất).
2. Tổng lớn nhất của đoạn con khác rỗng: Đoạn con là các phần tử liền kề nhau. Đây là bài toán quy hoạch động kinh điển (Maximum Subarray Sum - Kadane's Algorithm).

Các cách tiếp cận

Cách Tối ưu hóa Logic (Dựa trên Solution 1)

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
const int N = 1e6 + 10;

int max(int a, int b){
    return (a > b ? a : b);
}

int main(){
    int t; scanf("%d", &t);
    while(t--){     
        int n; scanf("%d", &n);
        int sum = 0, res = 0;
        int best = INT_MIN;
        int neg = INT_MIN, cneg = 0;
        for(int i = 1, a; i <= n; ++i){
            scanf("%d", &a);
            if(a >= 0) res += a;
            else{
                ++cneg;
                neg = max(neg, a);
            }
            sum = max(a, sum + a);
            best = max(best, sum);
        }
        if(cneg == n){
            printf("%d %d\n", neg, neg);
        }else printf("%d %d\n", res, best);
    }
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Phương pháp này giải quyết cả hai phần của bài toán trong một vòng lặp duy nhất.

• Phần 1 (Dãy con): Biến res cộng dồn tất cả các số dương (if(a >= 0)). Nếu tất cả đều là số âm (cneg == n), kết quả là số âm lớn nhất (được lưu trong neg).
• Phần 2 (Đoạn con): Sử dụng biến sum để lưu tổng đoạn con kết thúc tại vị trí hiện tại, và best để lưu tổng lớn nhất tìm được. Logic: sum = max(a, sum + a). Nếu sum tại hiện tại âm thì reset về a (bắt đầu đoạn mới).

Cách Phân tích Rõ ràng (Dựa trên Solution 2)

#include<stdio.h>
#include<math.h>
int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        int n;
        scanf("%d", &n);
        int a[n];
        for(int i=0; i<n; i++){
            scanf("%d", &a[i]);
        }
        long long sum1 = 0, sum2 = -1e9, max = -1e9, sum3 = 0;
        for(int i=0; i<n; i++){
            sum1 += a[i];
            if(sum1>sum2)
            sum2 = sum1;
            if(sum1<0)
            sum1 = 0;
        }
        for(int i=0; i<n; i++){
            if(a[i]>max)
            max = a[i];
        }
        if(max>0){
            for(int i=0; i<n; i++){
                if(a[i]>0)
                sum3 += a[i];
            }
        }
        else
            sum3 = max;
        printf("%lld %lld\n", sum3, sum2);
    }
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Cách tiếp cận này tách biệt logic hai phần:

• Đoạn con (sum2): Áp dụng thuật toán Kadane chuẩn. sum1 là tổng hiện tại, reset về 0 nếu âm. sum2 lưu max.
• Dãy con (sum3): Tìm giá trị lớn nhất (max) trước. Nếu max > 0, duyệt lại mảng để cộng các số dương. Nếu max <= 0, gán sum3 = max. Lưu ý: Solution 2 khai báo biến sum2 và max với giá trị ban đầu -1e9 (kiểu int) có thể gây lỗi số học nếu tổng vượt quá giới hạn, nhưng trong đề bài thì an toàn.

Cách Quy hoạch động Chuẩn (Phân tích thêm)

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    long long max_sub_sum = -1e18;
    long long cur_sum = 0;
    long long pos_sum = 0;
    bool has_positive = false;
    int max_neg = -1e9;

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

        // 1. Dãy con (tổng số dương)
        if (a[i] > 0) {
            pos_sum += a[i];
            has_positive = true;
        } else {
            max_neg = max(max, a[i]));
        }

        // 2. Đoạn con (Kadane)
        cur_sum += a[i];
        if (cur_sum > max_sub_sum) max_sub_sum = cur_sum;
        if (cur_sum < 0) cur_sum = 0;
    }

    long long ans1 = has_positive ? pos_sum : max_neg;
    cout << ans1 << " " << max_sub_sum << "\n";
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là phiên bản C++ hiện đại hóa của Logic 1, sử dụng long long để an toàn số học dù đề bài dùng int.

• Dãy con: Duyệt một lần, nếu a[i] > 0 thì cộng vào pos_sum, ngược lại cập nhật max_neg. Cuối cùng chọn pos_sum nếu có số dương, ngược lại chọn max_neg.
• Đoạn con: Dùng biến cur_sum (tổng hiện tại) và max_sub_sum. Nếu cur_sum < 0 thì reset về 0 (bắt đầu đoạn mới từ phần tử tiếp theo).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán dãy con (tổng lớn nhất) chỉ đơn giản là tổng các số dương. Quy tắc 'khác rỗng' bắt buộc phải chọn ít nhất 1 phần tử, nên nếu không có số dương ta phải chọn số âm lớn nhất.
• Bài toán đoạn con (tổng lớn nhất) có thể giải quyết trong O(N) bằng thuật toán Kadane. Logic cốt lõi là 'nếu tổng tích lũy hiện tại âm, ta nên bắt đầu một đoạn mới từ phần tử hiện tại'.
• Có thể kết hợp cả hai bài toán con vào cùng một vòng lặp duyệt mảng để tối ưu về mặt code và tốc độ.

Lỗi thường gặp

• Trường hợp toàn số âm: Cần xử lý riêng cho cả hai phần. Nếu không, phần dãy con sẽ trả về 0 (sai do rỗng) và phần đoạn con có thể sai nếu không khởi tạo đúng.
• Sai số kiểu dữ liệu: Mặc dù Input nằm trong int, nhưng tổng của dãy con có thể lên tới 10^9 (10^5 * 10^4). Khi dùng C/C++, nên dùng long long cho biến lưu tổng để tránh tràn số nếu test case lớn hơn một chút so với mô tả.
• Khởi tạo biến: Với Kadane algorithm, biến lưu tổng lớn nhất phải được khởi tạo bằng giá trị âm vô cùng (ví dụ: -1e18) hoặc phần tử đầu tiên của mảng.