Hướng dẫn giải của Trị tuyệt đối (Đề chọn ĐTQG Phú Thọ 2015-2016)
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
Cần tìm ~\max |S|~ với ~S~ là tổng của đoạn con liên tiếp. Ta có ~\max |S| = \max(\text{tổng đoạn lớn nhất}, -\text{tổng đoạn nhỏ nhất})~.
Sub 1: vét cạn mọi đoạn — ~O(n^2)~, dùng khi ~n \le 1000~
Với mỗi điểm đầu, cộng dần và cập nhật max |tổng|. Đúng 16/16 test.
Sub 2: Kadane hai lần — ~O(n)~
Tính đoạn con có tổng lớn nhất và nhỏ nhất bằng Kadane, đáp án là max của ~bestMax~ và ~-bestMin~. Đúng 16/16 test.
Chương trình hoàn chỉnh
main đọc n và dãy số. Nếu ~n \le 1000~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a;
// Sub 1: vet can moi doan lien tiep [i..j], tinh tong roi lay max |tong|. O(n^2). Dung khi n <= 1000.
void sub1() {
long long best = 0;
for (int i = 0; i < n; i++) {
long long s = 0;
for (int j = i; j < n; j++) {
s += a[j];
best = max(best, llabs(s));
}
}
cout << best << "\n";
}
// Sub 2: |tong| lon nhat = max(tong doan con lon nhat, -(tong doan con nho nhat)).
// Dung Kadane hai lan, O(n).
void sub2() {
long long curMax = 0, curMin = 0, bestMax = LLONG_MIN, bestMin = LLONG_MAX;
for (int i = 0; i < n; i++) {
curMax = max(a[i], curMax + a[i]);
curMin = min(a[i], curMin + a[i]);
bestMax = max(bestMax, curMax);
bestMin = min(bestMin, curMin);
}
cout << max(bestMax, -bestMin) << "\n";
}
int main() {
freopen("CAU3.INP", "r", stdin);
freopen("CAU3.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận