Hướng dẫn giải của LIST12: 3 số liên tiếp có tổng lớn nhất
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 ba số nguyên liên tiếp trong dãy n số (n ≤ 10^5, |A_i| ≤ 10^6), và in vị trí của ba số đó. Khi có nhiều đáp án, lấy vị trí đầu tiên.
Sub 1: Vét cạn trên mọi vị trí bắt đầu — ~O(n)~
Với mỗi vị trí bắt đầu i, cộng lại ba số Ai, A{i+1}, A_{i+2} bằng vòng lặp rồi cập nhật tổng lớn nhất (chỉ cập nhật khi lớn hơn để giữ vị trí đầu tiên). Đạ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;
// Vét cạn: với mỗi vị trí bắt đầu i, cộng lại 3 số liên tiếp bằng vòng lặp
long long best = LLONG_MIN;
int pos = 0;
for (int i = 0; i + 2 < n; i++) {
long long s = 0;
for (int k = i; k <= i + 2; k++) s += a[k];
if (s > best) { best = s; pos = i; } // chỉ cập nhật khi lớn hơn, lấy vị trí đầu tiên
}
cout << best << "\n" << pos + 1 << " " << pos + 2 << " " << pos + 3 << "\n";
return 0;
}
Sub 2: Cửa sổ trượt — ~O(n)~
Tính tổng ba số đầu tiên, sau đó mỗi lần dịch cửa sổ sang phải: bớt A{i−1} và thêm A{i+2}, nên không cần cộng lại từ đầu. Đạ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;
// Cửa sổ trượt: tổng 3 số bắt đầu từ i, chuyển sang i+1 bằng cách bớt a[i] và thêm a[i+3]
long long s = a[0] + a[1] + a[2];
long long best = s;
int pos = 0;
for (int i = 1; i + 2 < n; i++) {
s = s - a[i - 1] + a[i + 2];
if (s > best) { best = s; pos = i; } // lấy vị trí đầu tiên nếu có nhiều đáp án
}
cout << best << "\n" << pos + 1 << " " << pos + 2 << " " << pos + 3 << "\n";
return 0;
}
Bình luận