Hướng dẫn giải của [CSES 1643] Maximum Subarray Sum
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.
Chúng ta duyệt qua mảng và duy trì hai giá trị:
sum: tổng đoạn con lớn nhất kết thúc tại vị trí hiện tạibest: tổng đoạn con lớn nhất đã thấy từ trước đến nay
Giả sử giá trị tại vị trí ~i~ là ~x~ và ta muốn tính tổng đoạn con lớn nhất kết thúc tại vị trí ~i~. Ta có thể thực hiện điều này một cách hiệu quả khi biết tổng đoạn con lớn nhất kết thúc tại vị trí ~i-1~ trước đó: hoặc ta cộng ~x~ vào tổng trước đó, hoặc chỉ tạo một tổng chỉ gồm ~x~.
Lưu ý rằng đề bài yêu cầu đoạn con không rỗng, do đó ta phải nhớ rằng tổng lớn nhất cũng có thể là số âm.
#include <iostream>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
ll sum = -1e9;
ll best = -1e9;
for (int i = 1; i <= n; i++) {
ll x;
cin >> x;
sum = max(sum + x, x);
best = max(best, sum);
}
cout << best << "\n";
}
Tài liệu tham khảo
Chương trình tham khảo
#include <iostream>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
ll sum = -1e9;
ll best = -1e9;
for (int i = 1; i <= n; i++) {
ll x;
cin >> x;
sum = max(sum + x, x);
best = max(best, sum);
}
cout << best << "\n";
}
Bình luận