# README: Giải Quyết Bài Toán Dãy Con Lớn Nhất Sử Dụng Thuật Toán Kadane
## **Mục đích**
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ách giải chung**
Có nhiều cách giải cho bài toán này như:
- **Brute Force (Chạy trâu)**: Liệt kê tất cả các dãy con, tính tổng của từng dãy và chọn tổng lớn nhất. Phương pháp này có độ phức tạp là **O(n²)** hoặc **O(n³)**, vì phải duyệt qua tất cả các dãy con.
- **Dynamic Programming**: Sử dụng mảng `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.
- **Thuật toán Kadane**: Thuật toán này rất hiệu quả khi chỉ cần duyệt qua mảng một lần duy nhất với độ phức tạp **O(n)**.
Trong bài giải này, chúng ta sẽ sử dụng **Thuật toán Kadane**.
### **Mô tả thuật toán Kadane**:
- Duyệt qua dãy từ đầu đến cuối, theo lý thuyết của mảng cộng dồn: cộng hết vào một biến `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`.
- Biến `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
- Độ phức tạp thời gian O(n) và không gian O(1)
### **Tìm hiểu thêm về Kadane:**
Để hiểu rõ hơn về thuật toán Kadane, bạn có thể tham khảo bài viết [ở đây](https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/).
## **Mã C++**
```cpp
#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;
}
# README: Giải Quyết Bài Toán Dãy Con Lớn Nhất Sử Dụng Thuật Toán Kadane
## **Mục đích**
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ách giải chung**
Có nhiều cách giải cho bài toán này như:
- **Brute Force (Chạy trâu)**: Liệt kê tất cả các dãy con, tính tổng của từng dãy và chọn tổng lớn nhất. Phương pháp này có độ phức tạp là **O(n²)** hoặc **O(n³)**, vì phải duyệt qua tất cả các dãy con.
- **Dynamic Programming**: Sử dụng mảng `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.
- **Thuật toán Kadane**: Thuật toán này rất hiệu quả khi chỉ cần duyệt qua mảng một lần duy nhất với độ phức tạp **O(n)**.
Trong bài giải này, chúng ta sẽ sử dụng **Thuật toán Kadane**.
### **Mô tả thuật toán Kadane**:
- Duyệt qua dãy từ đầu đến cuối, theo lý thuyết của mảng cộng dồn: cộng hết vào một biến `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`.
- Biến `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.
### **Tìm hiểu thêm về Kadane:**
Để hiểu rõ hơn về thuật toán Kadane, bạn có thể tham khảo bài viết [ở đây](https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/).
## **Mã C++**
```cpp
#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;
}
Phatgivp10
Created at
1 likes