Hiểu bài toán

Bài toán yêu cầu tìm dãy con (không nhất thiết liên tiếp) sao cho hiệu số có dạng a{i1} - a{i2} + a{i3} - ... lớn nhất. Nói cách khác, ta cần chọn các số để tạo thành tổng có dấu âm dương xen kẽ, bắt đầu bằng dấu cộng. Ví dụ: chọn các chỉ số i1 < i2 < ... < ik thì điểm số là a[i1] - a[i2] + a[i3] - ... . Ta có thể chọn số lượng tùy ý các ô (kể cả 0).

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

Cách Quy hoạch động cơ bản (DP)

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

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

    // dp_pos: tổng lớn nhất khi dãy con kết thúc tại đây và có số lượng phần tử là LẺ
    // dp_neg: tổng lớn nhất khi dãy con kết thúc tại đây và có số lượng phần tử là CHẴN
    long long dp_pos = a[0];
    long long dp_neg = 0; // 0 phần tử (chẵn) có giá trị 0

    for(int i=1; i<n; i++) {
        long long new_pos = max(dp_pos, dp_neg + a[i]);
        long long new_neg = max(dp_neg, dp_pos - a[i]);
        dp_pos = new_pos;
        dp_neg = new_neg;
    }

    cout << dp_pos << endl;
    return 0;
}

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

Sử dụng 2 biến quy hoạch động: dp_pos lưu giá trị lớn nhất của tổng với dấu '+' (số lượng phần tử lẻ), dp_neg lưu giá trị lớn nhất với dấu '-' (số lượng phần tử chẵn). Tại mỗi bước, ta cập nhật:

1. new_pos: giữ nguyên dp_pos (bỏ qua phần tử hiện tại) hoặc lấy dp_neg + a[i] (đổi từ chẵn sang lẻ).
2. new_neg: giữ nguyên dp_neg hoặc lấy dp_pos - a[i] (đổi từ lẻ sang chẵn). Cuối cùng, đáp án là dp_pos.

Cách Quy hoạch động với mảng

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

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

    vector<vector<long long>> dp(n+1, vector<long long>(2, 0));
    dp[1][1] = a[1]; // Chọn phần tử đầu tiên

    for(int i=2; i<=n; i++) {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] - a[i]);
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] + a[i]);
    }

    cout << max(dp[n][0], dp[n][1]) << endl;
    return 0;
}

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

Cách tiếp cận này sử dụng mảng 2 chiều dp[n][2]. dp[i][0] là giá trị lớn nhất sau khi xét i phần tử với tổng số phần tử được chọn là chẵn. dp[i][1] là giá trị lớn nhất sau khi xét i phần tử với tổng số phần tử được chọn là lẻ. Công thức cập nhật:

• dp[i][0] = max(dp[i-1][0], dp[i-1][1] - a[i])
• dp[i][1] = max(dp[i-1][1], dp[i-1][0] + a[i]) Lưu ý: Code mẫu của người dùng có thể cần xử lý i=1 cẩn thận, nhưng về cơ bản logic là giữ lại trạng thái tốt nhất.

Cách Tối ưu hóa không gian (Optimized DP)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    long long odd = -1e18; // Trạng thái lẻ (dấu cộng)
    long long even = 0;     // Trạng thái chẵn (dấu cộng - trừ)

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        long long new_odd = max(odd, even + x);
        long long new_even = max(even, odd - x);

        odd = new_odd;
        even = new_even;
    }

    cout << odd << endl;
    return 0;
}

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

Đây là phiên bản tối ưu nhất của Quy hoạch động. Thay vì dùng mảng, ta chỉ cần 2 biến odd và even để lưu trạng thái của bước trước đó.

• odd: tổng lớn nhất có thể có với số lượng phần tử lẻ.
• even: tổng lớn nhất có thể có với số lượng phần tử chẵn. Tại mỗi số mới x:
• Nếu tiếp tục ở trạng thái odd hoặc chuyển từ even sang odd (cộng x): new_odd = max(odd, even + x).
• Nếu tiếp tục ở trạng thái even hoặc chuyển từ odd sang even (trừ x): new_even = max(even, odd - x). Đáp án cuối cùng là odd vì ta cần tổng bắt đầu bằng dấu cộng (số lượng phần tử lẻ).

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

Bài học kinh nghiệm

• Bài toán có thể chia thành 2 trạng thái chính dựa trên tính chẵn/lẻ của số lượng phần tử được chọn: trạng thái 'cộng' (+) và trạng thái 'trừ' (-).
• Luôn ưu tiên chọn phần tử nếu nó làm tăng tổng điểm hiện tại.
• Vì chỉ cần kết quả cuối cùng và số lượng phần tử có thể rất lớn, Quy hoạch động O(n) không gian O(1) là tối ưu.

Lỗi thường gặp

• Không khởi tạo giá trị ban đầu đúng cách. Ví dụ: dp_pos phải là số âm rất nhỏ (hoặc giá trị phần tử đầu tiên) để đảm bảo nếu tất cả các số đều âm, ta vẫn có thể chọn 1 phần tử thay vì chọn 0 phần tử (trừ khi chọn 0 phần tử cho phép, nhưng ở đây ta cần tối ưu bắt đầu bằng dấu cộng).
• Sử dụng biến có độ dài nhỏ (int) trong khi tổng có thể vượt quá 2^31-1. Nên dùng long long.
• Lầm tưởng rằng phải chọn các số liên tiếp. Đề bài cho phép chọn bất kỳ số lượng ô tùy ý từ trái qua phải, không cần liên tiếp.