Hiểu bài toán

Bài toán yêu cầu tìm đoạn con liên tiếp [i, j] của dãy số A sao cho giá trị F(i, j) + G(i, j) là lớn nhất, trong đó:

• F(i, j) = |ai| + |a{i+1}| + ... + |a_j| (tổng các giá trị tuyệt đối)
• G(i, j) = ai + a{i+1} + ... + a_j (tổng các số thực)

Tổng cần tối ưu là: Tổng{k=i}^j (|ak| + a_k)

Ta thấy rằng:

• Nếu ak >= 0, thì |ak| + ak = ak + ak = 2*ak
• Nếu ak < 0, thì |ak| + ak = -ak + a_k = 0

Vậy giá trị tại mỗi phần tử chỉ có ý nghĩa khi nó dương. Bài toán quy về tìm đoạn con liên tiếp có tổng lớn nhất (Maximum Subarray Sum) trên dãy số mới B, trong đó Bk = 2*ak nếu ak > 0, và Bk = 0 nếu a_k <= 0.

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

Cách Quy hoạch động Kadane

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    long long cur = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        // Chỉ xét giá trị dương, âm thì coi như 0
        long long val = max(0LL, 2 * x);
        // Cập nhật dãy con hiện tại: hoặc bắt đầu mới, hoặc nối tiếp
        cur = max(val, cur + val);
        // Cập nhật kết quả lớn nhất
        ans = max(ans, cur);
    }

    cout << ans;
    return 0;
}

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

Đây là thuật toán Kadane cải tiến. Thay vì xây dựng mảng B trước, ta duyệt trực tiếp từng phần tử. Với mỗi phần tử x:

1. Tính giá trị đóng góp thực tế: val = max(0, 2*x). Nếu x âm, đóng góp là 0.
2. Biến cur lưu tổng lớn nhất của đoạn con kết thúc tại vị trí hiện tại. Ta so sánh việc bắt đầu đoạn con mới tại đây (val) với việc nối tiếp đoạn con trước đó (cur + val).
3. Biến ans lưu giá trị lớn nhất tìm được từ đầu đến giờ.

Ví dụ với dãy [-3, 5, -10, 8, -2]:

• B: [0, 10, 0, 16, 0]
• Duyệt:
  • i=1 (x=-3): val=0, cur=max(0,0)=0, ans=0
  • i=2 (x=5): val=10, cur=max(10,0+10)=10, ans=10
  • i=3 (x=-10): val=0, cur=max(0,10+0)=10, ans=10
  • i=4 (x=8): val=16, cur=max(16,10+16)=26, ans=26
  • i=5 (x=-2): val=0, cur=max(0,26+0)=26, ans=26 Kết quả là 26.

Cách Dùng mảng tiền tố (Prefix Sum)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000000

ll n, a[N+3], pre[N+3], b[N+3];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for(ll i = 1; i <= n; i++) cin >> a[i];

    // Xây dựng mảng B và mảng tổng tiền tố
    for(ll i = 1; i <= n; i++){
        b[i] = a[i] + abs(a[i]); // Tương đương 2*max(a[i], 0)
        pre[i] = pre[i-1] + b[i];
    }

    ll mi = 0; 
    ll ma = 0;
    // Duyệt để tìm hiệu lớn nhất giữa pre[i] và min(pre[j]) với j < i
    for(ll i = 1; i <= n; i++){
        mi = min(mi, pre[i]);
        ma = max(ma, pre[i] - mi);
    }
    cout << ma << endl;
    return 0;
}

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

Phương pháp này dựa trên định lý: Tổng đoạn con từ j+1 đến i bằng pre[i] - pre[j]. Để tìm đoạn con có tổng lớn nhất, ta cần tìm i, j sao cho pre[i] - pre[j] là lớn nhất với j < i. Trong khi duyệt i từ 1 đến n, ta duy trì giá trị pre[j] nhỏ nhất tìm được (biến mi). Giá trị pre[i] - mi chính là tổng đoạn con kết thúc tại i có tổng lớn nhất. Ta cập nhật đáp án.

Phương pháp này cần O(n) bộ nhớ để lưu mảng trung gian, đây là nhược điểm so với Kadane.

Cách Dùng mảng trung gian

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

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

    // Chuyển đổi sang dãy B
    vector<ll> b(n);
    for(ll i=0; i<n; i++){
        if(a[i] > 0) b[i] = 2 * a[i];
        else b[i] = 0;
    }

    // Áp dụng Kadane trên mảng b
    ll cur = 0, ans = 0;
    for(ll x : b){
        cur = max(x, cur + x);
        ans = max(ans, cur);
    }
    cout << ans;
    return 0;
}

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

Đây là cách tiếp cận trực quan nhất.

1. Tạo một mảng mới b có kích thước n.
2. Duyệt mảng a, với mỗi phần tử:
   • Nếu a[i] > 0, gán b[i] = 2 * a[i].
   • Nếu a[i] <= 0, gán b[i] = 0.
3. Áp dụng thuật toán Kadane chuẩn (tìm đoạn con có tổng lớn nhất) trên mảng b.

Mặc dù đúng logic và dễ hiểu, cách này tốn bộ nhớ O(n) để lưu mảng b.

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

Bài học kinh nghiệm

• Bài toán có thể biến đổi thành bài toán tìm đoạn con liên tiếp có tổng lớn nhất (Maximum Subarray Sum) bằng cách thay a[i] bằng 2*a[i] nếu a[i] > 0 và 0 nếu a[i] <= 0.
• Hàm |x| + x bằng 0 khi x âm và bằng 2x khi x dương.

Lỗi thường gặp

• Quên xử lý số âm (phải coi như 0 thay vì tính |x| + x = -x + x = 0 nhưng có thể nhập nhằng logic).
• Sử dụng biến ans khởi tạo bằng 0. Nếu dãy chỉ toàn số âm, kết quả đúng là 0 (theo quy ước đoạn con rỗng hoặc chỉ chứa số 0). Tuy nhiên, nếu yêu cầu đoạn con không rỗng và dãy toàn số âm, cần khởi tạo ans = -INF. Nhưng với bài này, các giá trị đều >= 0 nên ans=0 là an toàn.
• Lỗi tràn số nguyên (overflow): a[i] lên tới 10^9, 2a[i] lên tới 210^9. Tổng dãy con có thể lên tới ~10^15. Cần dùng long long (64-bit).