Hướng dẫn giải của [Beginner Free Contest 04] SUB
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
Với mỗi test, cần hai giá trị: tổng lớn nhất của dãy con khác rỗng (không cần liên tiếp) và tổng lớn nhất của đoạn con liên tiếp khác rỗng.
Sub 1: Vét cạn — ~O(2^N \cdot N)~, dùng khi ~N \le 20~
Duyệt mọi tập con khác rỗng để lấy tổng lớn nhất; duyệt mọi đoạn ~[l..r]~ để lấy đoạn lớn nhất.
Nếu chỉ nộp sub này: đúng 10/20 test.
Sub 2: Tổng dương và Kadane — ~O(N)~
Dãy con lớn nhất: cộng tất cả số dương; nếu không có số dương thì lấy số lớn nhất. Đoạn con lớn nhất: thuật toán Kadane, ~cur = \max(a_i, cur + a_i)~.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Với mỗi test, nếu N \le 20 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 tap con khac rong (N <= 20) de lay tong lon nhat;
// vet can moi doan lien tiep de lay doan lon nhat. Dung khi N <= 20
void sub1() {
long long bestSub = LLONG_MIN, bestSeg = LLONG_MIN;
for (int mask = 1; mask < (1 << n); mask++) {
long long s = 0;
for (int i = 0; i < n; i++) if (mask >> i & 1) s += a[i];
bestSub = max(bestSub, s);
}
for (int l = 0; l < n; l++) {
long long s = 0;
for (int r = l; r < n; r++) {
s += a[r];
bestSeg = max(bestSeg, s);
}
}
cout << bestSub << " " << bestSeg << "\n";
}
// Sub 2: tong lon nhat cua day con khac rong = tong cac so duong (neu co so duong), neu khong thi lay so lon nhat.
// Tong lon nhat cua doan con lien tiep: thuat toan Kadane. O(N)
void sub2() {
long long pos = 0;
bool hasPos = false;
long long mx = LLONG_MIN;
for (int i = 0; i < n; i++) {
mx = max(mx, a[i]);
if (a[i] > 0) {
pos += a[i];
hasPos = true;
}
}
long long bestSub = hasPos ? pos : mx;
long long cur = 0, bestSeg = LLONG_MIN;
for (int i = 0; i < n; i++) {
cur = max(a[i], cur + a[i]);
bestSeg = max(bestSeg, cur);
}
cout << bestSub << " " << bestSeg << "\n";
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> n;
a.assign(n, 0);
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 20) sub1();
else sub2();
}
return 0;
}
Bình luận