Đoạn Con Tổng Lớn NhấtMaximum Subarray
Hiểu bài
Cho mảng nums (có thể có số âm). Tìm đoạn con liền kề (subarray) có tổng lớn nhất, trả về tổng đó.
Ví dụ:
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
// đoạn [4, -1, 2, 1] có tổng 6 — lớn nhất
output = 6Đoạn con phải liền nhau (không được bỏ phần tử ở giữa) và có ít nhất 1 phần tử.
Xem cách cơ bản (chậm hơn)
O(n²) time, O(1) spacefunction maxSubArray(nums: number[]): number {
let best = -Infinity
for (let i = 0; i < nums.length; i++) {
let sum = 0
for (let j = i; j < nums.length; j++) {
sum += nums[j]
best = Math.max(best, sum)
}
}
return best
}Thử mọi điểm bắt đầu i và cộng dồn tới mọi điểm kết thúc j.
Đúng nhưng với n=10⁵ thì n² = 10¹⁰ phép cộng — quá chậm.
Lời giải tối ưu
O(n) time, O(1) spacefunction maxSubArray(nums: number[]): number {
let curr = nums[0] // tổng đoạn tốt nhất KẾT THÚC tại i
let best = nums[0]
for (let i = 1; i < nums.length; i++) {
curr = Math.max(nums[i], curr + nums[i])
best = Math.max(best, curr)
}
return best
}- Thuật toán Kadane.
- Tại mỗi vị trí, hỏi: nên nối tiếp đoạn phía trước (
curr + nums[i]) hay bắt đầu lại từ chínhnums[i]? Nếucurrđang âm thì nó chỉ kéo tổng đi xuống → vứt đi, bắt đầu mới.bestghi lại giá trị lớn nhất từng thấy. - Tư duy tham lam: bỏ ngay tiền tố nào trở thành gánh nặng.
Chạy thử từng bước
- 1
Hình dung nums = [-2, 1, -3, 4, -1, 2].
Khởi tạo curr = best = nums[0] = −2.
i:0curr:-2best:-2 - 2
i=1 (1): curr = max(1, −2+1=−1) = 1 (bắt đầu lại tốt hơn nối). best = max(−2, 1) = 1.
i:1curr:1best:1 - 3
i=2 (−3): curr = max(−3, 1−3=−2) = −2. best vẫn 1. i=3 (4): curr = max(4, −2+4=2) = 4 → vứt tiền tố âm, bắt đầu lại. best = 4.
i:3curr:4best:4 - 4
i=4 (−1): curr = max(−1, 4−1=3) = 3. i=5 (2): curr = max(2, 3+2=5) = 5. best = max(4, 5) = 5.
Trả về 5 (đoạn [4,−1,2]).
i:5curr:5best:5result:5
Trường hợp biên phải nhớ
Mảng toàn số âm ([-3, -1, -2]) → đáp án là số âm lớn nhất (−1), KHÔNG phải 0.
Vì vậy khởi tạo bằng nums[0], đừng khởi tạo best = 0.
Mảng 1 phần tử → trả chính phần tử đó.
Khởi tạo
curr = 0rồi cộng là bẫy: với mảng toàn âm sẽ trả 0 sai.Phải so
Math.max(nums[i], curr + nums[i]).Số 0 xen kẽ không reset đoạn — chỉ tổng âm mới khiến nên bắt đầu lại.