Hướng dẫn giải của LIST11: Tổng lớn nhất của 2 số nguyên liên tiếp
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Tìm tổng lớn nhất của hai số nguyên liên tiếp trong dãy n số (n ≤ 10^5, |A_i| ≤ 10^6).
Sub 1: Vét cạn trên mọi cặp — ~O(n^2)~
Xét mọi cặp (i, j), chỉ lấy cặp có j = i + 1 và cập nhật tổng lớn nhất. Đạt 14/20 test (6 test còn lại quá giờ).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
// Vét cạn: xét mọi cặp (i, j), chỉ lấy cặp đứng liền nhau (j = i + 1)
long long best = LLONG_MIN;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (j == i + 1) best = max(best, a[i] + a[j]);
cout << best << "\n";
return 0;
}
Sub 2: Duyệt các cặp liền nhau — ~O(n)~
Chỉ cần duyệt i từ 2 đến n, so sánh A{i−1} + Ai với kết quả tốt nhất. Lưu ý các số có thể âm nên khởi tạo bằng tổng cặp đầu tiên, không khởi tạo bằng 0. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
// Duyệt các cặp liền nhau (a[i-1], a[i]) và lấy tổng lớn nhất
long long best = a[0] + a[1];
for (int i = 1; i + 1 < n; i++)
best = max(best, a[i] + a[i + 1]);
cout << best << "\n";
return 0;
}
Bình luận