Editorial for maxdiff: Xóa phần tử trong mảng

Hiểu bài toán

Cho một dãy số nguyên đã được sắp xếp tăng dần gồm n phần tử. Nhiệm vụ là xóa đúng một phần tử bất kỳ trong dãy sao cho 'độ đẹp' của dãy kết quả là lớn nhất có thể. 'Độ đẹp' được định nghĩa là giá trị hiệu lớn nhất giữa hai phần tử liên tiếp trong dãy.

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

Cách Brute Force (Mô phỏng từng trường hợp)

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;

    int max_beauty = 0;

    // Xóa từng phần tử (trừ đầu và cuối)
    for (int i = 1; i < n - 1; ++i) {
        int beauty = 0;
        for (int j = 1; j < n; ++j) {
            if (j == i || j - 1 == i) continue; // bỏ cặp liên quan đến phần tử bị xóa
            beauty = max(beauty, a[j] - a[j - 1]);
        }
        // thêm cặp mới do xóa a[i]
        beauty = max(beauty, a[i + 1] - a[i - 1]);
        max_beauty = max(max_beauty, beauty);
    }

    cout << max_beauty << '\n';
    return 0;
}

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

Cách tiếp cận này mô phỏng y chang hành động của con người. Với mỗi vị trí i có thể xóa (từ 1 đến n-2), ta duyệt qua toàn bộ mảng còn lại để tìm hiệu lớn nhất.

Cụ thể:

1. Vòng lặp for (int i = 1; i < n - 1; ++i) để chọn phần tử thứ i (bắt đầu từ 0) cần xóa. Ta không cần xét xóa phần tử đầu hoặc cuối vì theo tính chất tăng dần, hiệu lớn nhất thường nằm ở các đoạn giữa.
2. Trong mỗi lần xóa, ta duyệt mảng đã xóa (tức là bỏ qua a[i]) để tính max diff.
3. Do xóa a[i], cặp (a[i-1], a[i]) và (a[i], a[i+1]) biến mất, thay vào đó là cặp (a[i-1], a[i+1]). Ta phải so sánh cặp mới này với các cặp còn lại.

Độ phức tạp là O(n^2) do có 2 vòng lặp lồng nhau. Với n <= 1000, cách này chạy được nhưng không tối ưu.

Cách Quy hoạch động (Tối ưu hóa O(n))

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

int main (){
    long long n, a[1000001], ma = 0;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];

    // Chỉ cần xét các trường hợp xóa phần tử ở giữa
    for(int i = 2; i < n; i++)
        ma = max(ma, a[i+1] - a[i-1]);

    cout << ma;
    return 0;
}

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

Đây là phương pháp tối ưu nhất.

Bài toán quy về con: Khi ta xóa một phần tử a[i] (với 1 < i < n), dãy số sẽ gồm các phần tử từ a[1] đến a[i-1] nối tiếp a[i+1] đến a[n].

Tìm max diff:

1. Các cặp (a[k], a[k+1]) với k < i-1 giữ nguyên độ dài.
2. Các cặp (a[k], a[k+1]) với k > i giữ nguyên độ dài.
3. Một cặp mới được tạo ra do việc xóa a[i] là (a[i-1], a[i+1]). Khoảng cách của cặp này là a[i+1] - a[i-1].

Vì dãy ban đầu đã được sắp xếp tăng dần:

• Khoảng cách a[i+1] - a[i-1] chắc chắn lớn hơn hoặc bằng khoảng cách a[i] - a[i-1] và a[i+1] - a[i].
• Do đó, việc xóa a[i] có thể làm tăng độ đẹp (thông qua cặp mới) hoặc giữ nguyên độ đẹp (nếu cặp mới nhỏ hơn cặp khác).

Kết luận: Để tối đa hóa độ đẹp, ta chỉ cần quan tâm đến giá trị lớn nhất của a[i+1] - a[i-1] trong khoảng 2 <= i <= n-1. Ta duyệt qua các vị trí i có thể xóa, tính giá trị này và tìm max.

Lưu ý: Nếu chỉ xóa phần tử đầu hoặc cuối, độ đẹp của dãy mới chính là max diff của dãy cũ. Tuy nhiên, xóa ở giữa luôn tạo ra một khoảng cách ít nhất bằng hoặc lớn hơn một trong các khoảng cách ban đầu, nên ta chỉ cần tập trung vào việc tối đa hóa khoảng cách mới này.

Cách Đơn giản hóa (Duyệt kinh tế)

#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define sz size()
#define ll long long
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORD(i, a, b) for(int i = a; i >= b; --i)
#define F(i, a, b) for(int i = a; i < b; ++i)
#define FD(i, a, b) for(int i = a; i > b; --i)
#define faster() ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define Point pair<int,int>
#define vi vector<int>
#define vll vector<ll>
#define vb vector<bool>
#define endl '\n'
const int mod = 1e6 + 5;
const ll MOD = 1e9 + 7;

using namespace std;

int main(){
    int n;
    cin >> n;
    int a[n];
    F(i, 0, n) cin >> a[i];
    int val = INT_MIN;
    F(i, 0, n - 2){
        val = max(val, a[i + 2] - a[i]);
    }
    cout << val;
}

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

Đây là phiên bản tối ưu hóa về code và logic.

Vòng lặp F(i, 0, n - 2) chạy từ i = 0 đến n-3. Phép tính a[i + 2] - a[i] tương đương với việc xóa phần tử ở vị trí i+1 (trong mảng 0-index).

• Khi xóa a[i+1], 2 phần tử a[i] và a[i+2] trở nên liền kề nhau.
• Khoảng cách giữa chúng là a[i+2] - a[i].

Vòng lặp này lặp qua tất cả các trường hợp xóa phần tử ở giữa (từ phần tử thứ 1 đến thứ n-2, tính theo 1-index).

Giá trị val lưu lại khoảng cách lớn nhất có thể tạo ra khi xóa một phần tử ở giữa.

Độ phức tạp thời gian là O(n) và không gian là O(n) để lưu mảng.

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

Bài học kinh nghiệm

• Bài toán chỉ cần quan tâm đến việc xóa các phần tử ở giữa (không phải đầu hoặc cuối) vì xóa ở giữa tạo ra một khoảng cách mới là a[i+1] - a[i-1], khoảng cách này luôn lớn hơn hoặc bằng các khoảng cách bị xóa.
• Vấn đề được quy về tìm giá trị lớn nhất của hiệu a[i+1] - a[i-1] đối với i từ 2 đến n-1 (theo index 1).

Lỗi thường gặp

• Nhầm lẫn giữa chỉ số mảng (0-indexed) và số thự tự (1-indexed) khi tính toán khoảng cách mới.
• Bỏ qua trường hợp xóa phần tử đầu hoặc cuối, dù trong bài toán này nó không quan trọng bằng xóa ở giữa, nhưng cần hiểu rõ tại sao nó không cần thiết phải xét (vì giá trị trả về không thể lớn hơn giá trị tìm được ở giữa).