Đề bài: Dãy con có tổng dài nhất
Cho dãy số nguyên ~a_1, a_2, \dots, a_n~. Hãy tìm dãy con liên tiếp (subarray) có tổng lớn nhất.
Yêu cầu:
- Dãy con phải liên tiếp (định nghĩa dãy con)
- Có thể chọn dãy con chỉ gồm ~1~ phần tử
Ký hiệu tổng dãy con từ ~l~ đến ~r~ là: ~S(l,r) = a_l + a_{l+1} + \dots + a_r~.
Thuật toán "trâu"/"ngây thơ" (Thuần Brute-force)
Ý tưởng
- Xét mọi cặp ~l, r~ với ~1 \le l \le r \le n~, tính tổng dãy con ~[l, r]~, lấy giá trị lớn nhất.
Công thức
- ~\displaystyle S(l,r) = \sum_{i=l}^{r} a_i~.
Độ phức tạp thời gian
- Có ~\mathcal{O}(n^2)~ cặp ~l, r~:
- Mỗi lần tính tổng mất ~\mathcal{O}(n)~.
- Tổng: ~\mathcal{O}(n^3)~.
Nhận xét
- Cài đặt đơn giản.
- Tuy vậy chạy quá chậm, chỉ chạy được với ~n~ rất nhỏ.
Thuật toán “trâu” tối ưu (Brute-force nhưng tối ưu hơn)
Ý tưởng
- Vẫn duyệt mọi cặp ~l, r~, nhưng tối ưu cách tính tổng:
- Cố định ~l~.
- Sau đó mở rộng ~r~ dần và cộng dồn.
Mô tả
- Với mỗi ~l~:
- Khởi tạo ~\text{sum} = 0~.
- Với ~r~ từ ~l~ đến ~n~: ~\text{sum += } a_r~.
- Cập nhật kết quả.
Độ phức tạp thời gian
- Hai vòng lặp ~l, r~:
- Mỗi phép cộng ~\mathcal{O}(1)~.
- Tổng: ~\mathcal{O}(n^2)~.
Nhận xét
- Nhanh hơn rất nhiều so với thuật toán ngây thơ.
- Vẫn chưa đủ tốt nếu ~n~ lớn ~(10^5)~.
Quy hoạch động Kadane (Kadane's Dynamic Programming)
Ý tưởng
- Xét bài toán con:
- Gọi ~dp[i]~ là tổng lớn nhất của dãy con kết thúc tại vị trí ~i~.
- Tại ~i~, ta có hai lựa chọn:
- Bắt đầu dãy con mới tại ~i~.
- Nối ~a_i~ vào dãy con tốt nhất kết thúc tại ~i-1~.
- Công thức truy hồi: ~\text{dp}[i] = \max(a_i, \text{dp}[i-1] + a_i)~.
- Kết quả cuối cùng: ~\text{ans} = \displaystyle \max_{1 \le i \le n} \text{dp}[i]~.
Độ phức tạp thời gian và không gian
- Thời gian: ~\mathcal{O}(n)~.
- Bộ nhớ: ~\mathcal{O}(n)~ (có thể tối ưu xuống ~\mathcal{O}(1)~).
Nhận xét
- Hiệu quả, nhanh đét.
Tổng tiền tố (Prefix Sum)
Ý tưởng
- Ta cần tối đa hóa: ~\max(S(l, r)) = \max (\text{pref}[r] - \text{pref}[l - 1])~.
- Với mỗi ~r~, muốn giá trị này lớn nhất thì ~\text{pref}[l - 1]~ phải nhỏ nhất trước đó.
Cài đặt
- Duyệt ~r~ từ ~1~ đến ~n~.
- Luôn lưu ~\text{minPref}~ là giá trị nhỏ nhất của ~\text{pref}~ đã gặp.
- Cập nhật: ~\text{ans} = \max(\text{ans}, \text{pref}[r] - \text{minPref})~.
Độ phức tạp thời gian và không gian
- Thời gian: ~\mathcal{O}(n)~.
- Bộ nhớ: ~\mathcal{O}(n)~ (hoặc ~\mathcal{O}(1)~ nếu tối ưu).
Nhận xét
- Bản chất tương đương Kadane.
Bình luận