CTDL & giải thuật

Kadane: đoạn con có tổng lớn nhất trong O(n)

Một đoạn con tối ưu kết thúc tại vị trí hiện tại chỉ có hai lựa chọn: nối vào đoạn trước hoặc bắt đầu lại. Kadane nén quy hoạch động này thành vài biến.

Một trạng thái đủ cho đoạn con tốt nhất

Đoạn con phải liên tiếp. Khi xét a[i], đoạn tốt nhất kết thúc đúng tại i chỉ có hai khả năng: bắt đầu mới ở i, hoặc nối a[i] vào đoạn tốt nhất kết thúc tại i-1. Kadane nén quy hoạch động này thành cur, best và vài chỉ số.

Ý chính

Khởi tạo bằng phần tử đầu, không bằng 0. Nhờ vậy mảng toàn số âm trả phần tử âm lớn nhất thay vì đoạn rỗng không được phép.

Kadane: Đoạn tối ưu [3, 7) = [4, -1, 2, 1] có tổng = 6 -2cur=-2 1cur=1 -3cur=-2 4cur=4 -1cur=3 2cur=5 1cur=6 -5cur=1 4cur=5 Khi cur < 0: mở đoạn mới Tại i = 3: start = 3, cur = 4 Khi cur ≥ 0: nối tiếp a[i] Tại i = 6: best = 6 trên [3, 7) Khởi tạo cur = best = a[0] · Thời gian O(n), bộ nhớ O(1)
Kadane: [-2, 1, -3, 4, -1, 2, 1, -5, 4] Sau i = 2 (-3): cur = -2 < 0 Tổng âm làm giảm đoạn kế tiếp Tại i = 3 (a[3] = 4) Mở đoạn mới: start = 3, cur = 4 Đoạn [3, 7) = [4, -1, 2, 1] cur: 4 → 3 → 5 → 6 (best = 6) Đáp án: 6 [3, 7) · O(n)
Hình 1. Diễn biến biến cur, best và đoạn tối ưu [3, 7) có tổng bằng 6 trên mảng 9 phần tử.

Công thức từ định nghĩa

Gọi end[i] là tổng lớn nhất của đoạn không rỗng kết thúc tại i. Khi đó end[i]=max(a[i],end[i-1]+a[i]). Đáp án là max của mọi end[i]. Không cần lưu cả mảng vì trạng thái mới chỉ phụ thuộc trạng thái trước; cur giữ end hiện tại và best giữ giá trị tốt nhất đã thấy.

Bản mẫu viết tương đương: nếu cur cũ âm thì bỏ nó và bắt đầu tại a[i], nếu không âm thì nối. Khi bắt đầu lại, cập nhật start=i. Chỉ khi cur lớn hơn best mới chép start sang L và i+1 sang R. Dùng dấu > thay vì >= tạo quy tắc hòa: giữ đoạn gặp trước.

Mảng -2,1,-3,4,-1,2,1,-5,4 cho best 6 trên [3,7), gồm 4,-1,2,1. Sau -3, cur âm nên 4 mở đoạn mới. Ba số kế tiếp vẫn làm tổng tăng; thêm -5 giảm tổng nhưng không xóa best đã lưu.

Ca toàn âm phân biệt bản đúng

Với -8,-2,-5,-9, mọi đoạn dài hơn không thể tốt hơn -2. Khởi tạo cur=best=a[0] rồi áp dụng công thức trả -2 [1,2). Nếu khởi tạo best=0, chương trình sẽ trả 0, ngầm cho phép đoạn rỗng dù đề yêu cầu không rỗng.

Nếu đề thật sự cho phép chọn rỗng, khởi tạo 0 là hợp lệ nhưng hợp đồng và biên đáp án phải thay đổi. Không có một lựa chọn đúng cho mọi đề; cần đọc câu “đoạn con không rỗng” trước khi dùng mẫu.

#include <iostream>
#include <tuple>
#include <vector>
using namespace std;using ll=long long;
tuple<ll,int,int> kadane(const vector<ll>&a){ll cur=a[0],best=a[0];int start=0,L=0,R=1;for(int i=1;i<(int)a.size();++i){if(cur<0){cur=a[i];start=i;}else cur+=a[i];if(cur>best){best=cur;L=start;R=i+1;}}return {best,L,R};}
int main(){int n=9;vector<ll>a={-2,1,-3,4,-1,2,1,-5,4};if(cin>>n){a.resize(n);for(auto&x:a)cin>>x;}auto[s,l,r]=kadane(a);cout<<s<<' '<<l<<' '<<r<<'\n';}

Thuật toán chạy một lượt O(n), bộ nhớ phụ O(1). C++ dùng long long; tổng n phần tử 32 bit có thể vượt int. Đầu ra gồm tổng, L và R theo đoạn nửa mở 0-based, giúp độ dài bằng R-L và cắt mảng Python trực tiếp.

Bất biến để tự viết lại

Sau khi xử lý i, cur là tổng lớn nhất trong mọi đoạn kết thúc đúng tại i; start là đầu đoạn đạt cur. best là tổng lớn nhất trong mọi đoạn nằm hoàn toàn trong [0,i]; [L,R) là một đoạn đạt best. Hai mệnh đề này cho phép chứng minh bằng quy nạp.

Ở bước i+1, mọi đoạn kết thúc tại đó hoặc chỉ có a[i+1], hoặc là một đoạn kết thúc tại i nối thêm a[i+1]. Trong nhóm thứ hai chỉ cần đoạn có tổng lớn nhất, vì cộng cùng một số giữ thứ tự. Đó là lý do một trạng thái cur đủ.

Cẩn thận

Kadane giải đoạn con liên tiếp, không giải dãy con được phép bỏ vị trí ở giữa. Với dãy con tổng lớn nhất, các số dương có thể được chọn độc lập và mô hình khác hẳn.

Quy tắc hòa và truy vết

Nhiều đề chỉ hỏi tổng nên mọi đoạn tối ưu đều được chấp nhận. Khi phải in biên, cần định nghĩa hòa: trái nhỏ nhất, ngắn nhất hay dài nhất. Code hiện giữ đáp án xuất hiện sớm vì chỉ cập nhật khi cur>best. Nếu cần ngắn nhất, so thêm độ dài khi tổng bằng; nếu cần từ điển (L,R) nhỏ nhất, so cặp chỉ số rõ ràng.

Đừng gán start=i ngay khi cur vừa âm sau khi cộng a[i]: đoạn mới phải bắt đầu từ phần tử kế tiếp. Trong code, start chỉ đổi ở bước sau, đúng lúc bỏ cur cũ và lấy cur=a[i]. Viết theo hai lựa chọn a[i] và cur+a[i] thường dễ kiểm hơn các biến thể reset về 0.

Học cùng giảng viên

Chủ đề này nằm trong Lecture 04: Divide and Conquer (Chia để trị) của Khóa Orange. Xem đề cương

Các biến thể quan trọng

Đoạn con vòng tròn: đáp án là max của Kadane thường và tổng toàn mảng trừ đoạn có tổng nhỏ nhất, nhưng phải xử lý toàn âm để không chọn phần bù rỗng. Cho phép xóa tối đa một phần tử cần hai trạng thái: chưa xóa và đã xóa. Tổng lớn nhất trên ma trận dùng cặp hàng, nén cột rồi chạy Kadane, thường O(rows²·cols).

Segment Tree có thể trả lời đoạn tốt nhất sau cập nhật nếu mỗi nút lưu tổng, prefix tốt nhất, suffix tốt nhất và subarray tốt nhất. Phép gộp cần xét đoạn tốt nhất nằm trái, nằm phải hoặc nối suffix trái với prefix phải.

Tự kiểm tra bằng cách duyệt mọi cặp đầu mút O(n²)

Để kiểm tra cả tổng lớn nhất lẫn hai chỉ số truy vết [L, R), bạn có thể viết một hàm hai vòng lặp liệt kê mọi cặp 0 <= l < r <= n (độ dài r - l > 0), tính tổng đoạn a[l..r) và cập nhật đáp án theo đúng quy tắc ưu tiên khi hòa. Hãy thử ít nhất ba nhóm dữ liệu: mảng hỗn hợp âm dương chuẩn, mảng toàn số âm và mảng toàn số 0. Kết quả của hàm Kadane phải khớp cả ba giá trị (best, L, R), không chỉ riêng tổng lớn nhất.

Một trường hợp rất đáng thử nữa là mảng có nhiều đoạn con rời nhau cùng đạt tổng cực đại. Ca này kiểm tra xem điều kiện cập nhật cur > best và thời điểm gán lại start = i đã nhất quán với quy tắc hòa hay chưa, tránh tình trạng tổng đúng nhưng biên [L, R) bị lệch sang đoạn sau.

Bạn có thể sinh ngẫu nhiên vài trăm mảng ngắn độ dài tối đa 12 với giá trị trong đoạn [-5, 5] để tạo thật nhiều trường hợp bằng tổng. Nếu muốn đổi sang quy tắc ưu tiên đoạn ngắn nhất hoặc đoạn xuất hiện muộn nhất, hãy sửa điều kiện ở hàm duyệt O(n²) trước rồi chỉnh hàm Kadane tới khi hai bên cho kết quả giống hệt nhau.

Bảng trạng thái Kadane từng bước

Với [-2,1,-3,4,-1,2,1,-5,4], lập ba cột cur, start, best. Tại số 4, cur cũ âm nên đoạn mới bắt đầu ở chỉ số 3. Sau khi đọc 1 ở chỉ số 6, best bằng 6 trên [3,7).

Ca biên Kết quả cần có
[-8,-2,-5] -2, không phải 0
[0,0,0] tổng 0 và biên theo quy tắc hòa
[5] 5 trên [0,1)
[3,-1,3] 5 trên toàn đoạn

Để tự kiểm, liệt kê mọi cặp l < r khi n nhỏ, cộng a[l:r] và áp dụng đúng cùng quy tắc hòa. So cả tổng lẫn hai biên; chỉ so tổng sẽ bỏ sót lỗi truy vết.

Từ Kadane tới cây đoạn

Khi mảng có cập nhật, chạy lại Kadane sau mỗi lần đổi là O(n). Segment Tree có thể giữ bốn đại lượng ở mỗi nút: tổng toàn đoạn, prefix tốt nhất, suffix tốt nhất và subarray tốt nhất. Khi gộp hai con, đoạn tối ưu hoặc nằm trọn một bên, hoặc nối suffix trái với prefix phải.

Quy ước đoạn rỗng tiếp tục ảnh hưởng giá trị lá và phần tử trung hòa. Nếu bài yêu cầu không rỗng, một lá mang chính a[i] cho ba giá trị tốt nhất; nút rỗng phải dùng âm vô cùng đúng chỗ. Nếu cho phép rỗng, có thể chặn các giá trị bằng 0. Trộn hai hợp đồng sẽ tái tạo lỗi mảng toàn âm ở cấp cây.

Với mảng vòng tròn, đáp án có thể là Kadane thường hoặc tổng toàn mảng trừ đoạn tổng nhỏ nhất. Nhưng nếu mọi số âm, phần bù này là đoạn rỗng và không hợp lệ; phải trả phần tử lớn nhất. Viết riêng ca toàn âm trước khi dùng công thức giúp tránh một ngoại lệ dễ quên.

Truy vết đoạn đáp án

Ngoài tổng lớn nhất, nhiều đề yêu cầu hai đầu đoạn. Hãy giữ start của đoạn đang chạy; khi quyết định bắt đầu lại tại i, gán start=i. Mỗi lần cập nhật đáp án tốt nhất, chép cả start và i. Nếu có nhiều đoạn cùng tổng, quy tắc ưu tiên đoạn ngắn hơn hay chỉ số nhỏ hơn phải được đưa vào điều kiện so sánh, không nên để phụ thuộc tình cờ vào dấu > hoặc >=.

Luyện ngay trên Big-O Coding

Ba bài dưới đây đều hỏi đúng tổng đoạn con lớn nhất.

Ba đề đều trực tiếp hỏi tổng đoạn con lớn nhất; hãy bắt đầu bằng bản chỉ lấy tổng, rồi tự thêm truy vết biên và ca toàn âm.

Câu hỏi thường gặp

Kadane có phải DP không?

Có. Nó là DP một chiều được tối ưu bộ nhớ từ mảng end xuống một biến.

Vì sao reset khi cur âm?

Một tổng âm chỉ làm mọi đoạn nối sau đó nhỏ hơn bắt đầu mới tại cùng vị trí kế tiếp.

Nếu mảng rỗng thì sao?

Hợp đồng code yêu cầu n>=1. Nếu ứng dụng cho mảng rỗng, phải định nghĩa kết quả riêng trước khi gọi.

Muốn học bài bản cùng giảng viên?

Khóa Orange: làm chủ thuật toán nâng cao như Graph, DP tối ưu, Segment Tree, HLD để giải bài Hard. 16 buổi online, C++/Java/Python, học thử buổi 1 miễn phí.

Xem Khóa Orange

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483