Select solution language
Bài toán tìm dãy con lớn nhất trong một dãy số cho trước. Dãy con này có thể không liên tiếp, và bài toán yêu cầu tìm tổng lớn nhất của dãy con liên tiếp đó.
Trong bài giải này, tôi sẽ sử dụng Thuật toán Kadane, một giải pháp tối ưu để giải quyết bài toán này với độ phức tạp thời gian O(n).
Có nhiều cách giải cho bài toán này như:
dp
để lưu trữ kết quả con bài toán con và xây dựng kết quả dần dần.Trong bài giải này, chúng ta sẽ sử dụng Thuật toán Kadane.
res
. Tuy nhiên, thuật toán này không cộng tất cả như prefix sum thông thường, mà chỉ tìm tổng lớn nhất có thể của tất cả subarray kết thúc ở vị trí i
.res
sẽ là giá trị lớn nhất của tất cả những phần tử này tại mỗi bướcĐể hiểu rõ hơn về thuật toán Kadane, bạn có thể tham khảo bài viết ở đây.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
// author: Phat
// github: SingularDuo
// Hàm thực hiện thuật toán Kadane
ll kadane(vector<ll>& a) {
ll res = a[0], maxend = a[0]; // khởi tạo kết quả và giá trị tạm thời
for(int i = 1; i < a.size(); i++) {
maxend = max(a[i], maxend + a[i]); // chọn max giữa phần tử hiện tại và maxend cộng với phần tử hiện tại
res = max(res, maxend); // cập nhật res nếu cần
}
return res; // trả về tổng lớn nhất
}
void sol() {
ll n;
cin >> n; // đọc số phần tử trong dãy
vector<ll> a(n);
for(int i = 0; i < n; i++) cin >> a[i]; // nhập dãy số
cout << kadane(a); // gọi hàm Kadane và in kết quả
return;
}
signed main() {
sol(); // gọi hàm giải quyết bài toán
return 0;
}
Bài toán tìm dãy con lớn nhất trong một dãy số cho trước. Dãy con này có thể không liên tiếp, và bài toán yêu cầu tìm tổng lớn nhất của dãy con liên tiếp đó.
Trong bài giải này, tôi sẽ sử dụng Thuật toán Kadane, một giải pháp tối ưu để giải quyết bài toán này với độ phức tạp thời gian O(n).
Có nhiều cách giải cho bài toán này như:
dp
để lưu trữ kết quả con bài toán con và xây dựng kết quả dần dần.Trong bài giải này, chúng ta sẽ sử dụng Thuật toán Kadane.
res
. Tuy nhiên, thuật toán này không cộng tất cả như prefix sum thông thường, mà chỉ tìm tổng lớn nhất có thể của tất cả subarray kết thúc ở vị trí i
.res
sẽ là giá trị lớn nhất của tất cả những phần tử này tại mỗi bước.Để hiểu rõ hơn về thuật toán Kadane, bạn có thể tham khảo bài viết ở đây.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
// author: Phat
// github: SingularDuo
// Hàm thực hiện thuật toán Kadane
ll kadane(vector<ll>& a) {
ll res = a[0], maxend = a[0]; // khởi tạo kết quả và giá trị tạm thời
for(int i = 1; i < a.size(); i++) {
maxend = max(a[i], maxend + a[i]); // chọn max giữa phần tử hiện tại và maxend cộng với phần tử hiện tại
res = max(res, maxend); // cập nhật res nếu cần
}
return res; // trả về tổng lớn nhất
}
void sol() {
ll n;
cin >> n; // đọc số phần tử trong dãy
vector<ll> a(n);
for(int i = 0; i < n; i++) cin >> a[i]; // nhập dãy số
cout << kadane(a); // gọi hàm Kadane và in kết quả
return;
}
signed main() {
sol(); // gọi hàm giải quyết bài toán
return 0;
}