Hướng dẫn giải của [Beginner Free Contest 01] MAXSUM
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
Cho mảng A gồm N phần tử (N <= 1000, A_i có thể âm). Tìm đoạn liên tiếp có tổng lớn nhất và in tổng đó.
Sub 1: Thử mọi đoạn [i..j], cộng từng phần tử — ~O(n^3)~
Ba vòng lặp: chọn đầu i, cuối j, cộng các phần tử từ i đến j rồi cập nhật max. Đúng vì N <= 1000 nhưng chậm.
Kết quả chấm: đạ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;
long long best = LLONG_MIN;
// Vet can: thu moi doan [i..j], cong tung phan tu (O(n^3))
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++) {
long long s = 0;
for (int t = i; t <= j; t++) s += a[t];
best = max(best, s);
}
cout << best << endl;
return 0;
}
Sub 2: Cộng dồn theo điểm đầu — ~O(n^2)~
Với mỗi đầu i, cộng dần các phần tử j = i, i+1, ... và cập nhật max sau mỗi bước, tránh vòng lặp thứ ba.
Kết quả chấm: đạ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;
long long best = LLONG_MIN;
// Voi moi diem bat dau i, cong dan cac phan tu j (O(n^2))
for (int i = 0; i < n; i++) {
long long s = 0;
for (int j = i; j < n; j++) {
s += a[j];
best = max(best, s);
}
}
cout << best << endl;
return 0;
}
Sub 3: Kadane — ~O(n)~
cur là tổng đoạn lớn nhất kết thúc tại i: cur = max(ai, cur + ai), best = max(best, cur). Bẫy: mảng có số âm nên phải khởi tạo bằng a_0 chứ không phải 0, vì đoạn phải chứa ít nhất một phần tử.
Kết quả chấm: đạ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;
// Kadane: cur la tong doan lien tiep ket thuc tai i; neu cur am thi bat dau lai
long long cur = a[0], best = a[0];
for (int i = 1; i < n; i++) {
cur = max(a[i], cur + a[i]);
best = max(best, cur);
}
cout << best << endl;
return 0;
}
Bình luận