giúp vs ạ

Hôm nay Bờm được học về dãy số. Thầy giáo đố Bờm bài toán sau: Cho dãy số nguyên a1, a2, .., aN. Hãy tìm giá trị lớn nhất của S = |ai + aj + ak|, trong đó i, j, k là các số đôi một khác nhau (1 ≤ i, j, k ≤ N).

Dữ liệu: Vào từ tệp văn bản TONGMAX.INP gồm:

• Dòng đầu tiên chứa duy nhất một số nguyên dương N (3 ≤ N ≤ 5.10^6);

• Dòng thứ hai chứa N số nguyên a1, a2, .., aN (|ai| ≤ 10^9, ∀i = 1..N).

Kết quả: Ghi ra tệp văn bản TONGMAX.OUT duy nhất một số là giá trị lớn nhất của S tìm được.

Ví dụ:

TONGMAX.INP

5

1 -2 3 4 5

TONGMAX.OUT

12

Giải thích

S = |3 + 4 + 5| = 12

Ràng buộc:

• Có 60% số test tương ứng với 60% số điểm của bài có N ≤ 10^2;

• Có 20% số test tương ứng với 20% số điểm của bài có N ≤ 10^5;

• Có 20% số test tương ứng với 20% số điểm của bài có N ≤ 5.10^6

Đáp án:

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

typedef long long ll;

int main() {
    ifstream infile("TONGMAX.INP");
    ofstream outfile("TONGMAX.OUT");

    ll N;
    infile >> N;

    vector<ll> a(N);
    for(ll i = 0; i < N; ++i) {
        infile >> a[i];
    }

    sort(a.begin(), a.end());

    ll max1 = a[N-1], max2 = a[N-2], max3 = a[N-3];
    ll min1 = a[0], min2 = a[1], min3 = a[2];

    ll S1 = abs(max1 + max2 + max3);
    ll S2 = abs(min1 + min2 + min3);
    ll S3 = abs(max1 + max2 + min1);
    ll S4 = abs(min1 + min2 + max1);

    ll result = max({S1, S2, S3, S4});

    outfile << result;

    infile.close();
    outfile.close();

    return 0;
}

Giải thích các bước giải:

Do yêu cầu tính giá trị tuyệt đối lớn nhất của tổng ba phần tử, một cách tiếp cận hiệu quả là tập trung vào các giá trị lớn nhất và nhỏ nhất trong mảng:

1. Sắp xếp mảng: Khi sắp xếp mảng, các giá trị lớn nhất sẽ nằm ở cuối và các giá trị nhỏ nhất sẽ nằm ở đầu.
2. Xét các tổ hợp: Chúng ta chỉ cần xét một vài tổ hợp của các phần tử lớn nhất và nhỏ nhất trong mảng để tìm giá trị tuyệt đối lớn nhất.