Tổng Lớn Nhất Mảng Con Kích Thước KMaximum Subarray of Size K
Hiểu bài
Cho bạn một mảng số nguyên nums và số nguyên k. Tìm tổng lớn nhất của mảng con liên tiếp có đúng k phần tử.
Ví dụ:
nums = [2, 1, 5, 1, 3, 2], k = 3
output = 9 // mảng con [5, 1, 3] có tổng 5+1+3 = 9
nums = [2, 3, 4, 1, 5], k = 2
output = 7 // mảng con [3, 4] có tổng 3+4 = 7Đây là bài nhập môn cho kỹ thuật Cửa sổ trượt (Sliding Window) — cửa sổ kích thước cố định di chuyển từ trái sang phải.
Xem cách cơ bản (chậm hơn)
O(n·k) time, O(1) spacefunction maxSubarrayOfSizeK(nums: number[], k: number): number {
let maxSum = -Infinity
for (let i = 0; i <= nums.length - k; i++) {
let windowSum = 0
for (let j = i; j < i + k; j++) {
windowSum += nums[j]
}
maxSum = Math.max(maxSum, windowSum)
}
return maxSum
}Với mỗi vị trí bắt đầu, ta cộng lại k phần tử từ đầu.
- Khi k lớn (gần n) thì gần O(n²).
- Cửa sổ trượt loại bỏ sự tính toán thừa này.
Lời giải tối ưu
O(n) time, O(1) spacefunction maxSubarrayOfSizeK(nums: number[], k: number): number {
let windowSum = 0
let maxSum = -Infinity
let left = 0
for (let right = 0; right < nums.length; right++) {
windowSum += nums[right] // mở rộng cửa sổ sang phải
if (right >= k - 1) { // cửa sổ đủ k phần tử
maxSum = Math.max(maxSum, windowSum)
windowSum -= nums[left] // thu nhỏ từ trái
left++
}
}
return maxSum
}Cách tối ưu dùng Cửa sổ trượt (Sliding Window) kích thước cố định k: mỗi bước cộng phần tử mới vào phải, trừ phần tử cũ ở trái.
Không cộng lại từ đầu, mỗi phần tử chỉ xử lý đúng 1 lần.
Chạy thử từng bước
- 1
right=0: windowSum=2.
Chưa đủ k=3 phần tử, bỏ qua.
left:0right:0windowSum:2maxSum:-Infinity - 2
right=1: windowSum=2+1=3.
Chưa đủ k=3.
left:0right:1windowSum:3maxSum:-Infinity - 3
right=2: windowSum=3+5=8. right>=k-1=2 → maxSum=8, trừ nums[0]=2, left=1. windowSum=6.
left:1right:2windowSum:6maxSum:8 - 4
right=3: windowSum=6+1=7. maxSum=max(8,7)=8, trừ nums[1]=1, left=2. windowSum=6.
left:2right:3windowSum:6maxSum:8 - 5
right=4: windowSum=6+3=9. maxSum=max(8,9)=9, trừ nums[2]=5, left=3. windowSum=4.
left:3right:4windowSum:4maxSum:9 - 6
right=5: windowSum=4+2=6. maxSum=max(9,6)=9.
Kết quả: 9.
left:4right:5windowSum:6maxSum:9
Trường hợp biên phải nhớ
k bằng độ dài mảng — cả mảng là một cửa sổ duy nhất, trả về tổng toàn bộ mảng.
k=1 — trả về phần tử lớn nhất trong mảng.
Tất cả phần tử âm — vẫn chạy đúng vì maxSum khởi đầu từ -Infinity.
k lớn hơn độ dài mảng — vòng lặp if (right >= k-1) không bao giờ được thực thi, maxSum không được cập nhật; cần validate k ≤ n trước.